• 欧拉函数 HDU 1286 HDU 2588 HDU 2824 HDU 4983
HDU 1286：
素数筛+欧拉函数版本：
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 33000;
bool vis[33333];
int p[33333];

void prime(int n) {
memset(vis, false, sizeof(vis));
memset(p, 0, sizeof(p));
int pos = 0;
for(int i = 2; i <= n; ++i) {
if(!vis[i]) p[pos++] = i;
for(int j = 0; j < pos && i * p[j] <= n; ++j) {
vis[p[j] * i] = true;
if(i % p[j] == 0) break;
}
}
}

int Euler(int n) {
int ans = n;
for(int i = 0; p[i] * p[i] <= n; ++i) {
if(n % p[i] == 0) {
ans = ans - ans / p[i];
while(n % p[i] == 0) n /= p[i];
}
}
if(n > 1) {
ans = ans - ans / n;
}
return ans;
}

int main() {
int T;
prime(33333);
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
printf("%d\n", Euler(n));
}
return 0;
}
HDU 2588：
#include <bits/stdc++.h>

// X must be a factor of N
using namespace std;

int Euler(int n) {
int ans = n;
for(int i = 2; i * i <= n; ++i) {
if(n % i == 0) {
ans = ans - ans / i;
while(n % i == 0) {
n /= i;
}
}
}
if(n > 1) ans = ans - ans / n;
return ans;
}

int main() {
int T;
scanf("%d ", &T);
while(T--) {
int n, m;
scanf("%d %d", &n, &m);
int sum = 0;
for(int i = 1; i * i <= n; ++i) {
if(n % i == 0) {
if(i >= m) sum += Euler(n / i);
if((n / i) != i && (n / i) >= m) sum += Euler(i);  // Whether N is a square number
}
}
printf("%d\n", sum);
}
return 0;
}
HDU 2824：
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3333333;
int phi[MAXN];

void Euler() {
for(int i = 1; i <= 3300000; ++i) phi[i] = i;
for(int i = 2; i <= 3300000; i += 2) phi[i] /= 2;
for(int i = 3; i <= 3300000; i += 2) {
if(phi[i] == i) {
for(int j = i; j <= 3300000; j += i) {
phi[j] = phi[j] / i * (i - 1);
}
}
}
}

int main() {
Euler();
int a, b;
while(scanf("%d %d", &a, &b) != EOF) {
long long sum = 0;
for(int i = a; i <= b; ++i) {
sum += phi[i];
}
printf("%lld\n", sum);
}
return 0;
}
HDU  4983:
#include <bits/stdc++.h>

using namespace std;
const int MOD = 1000000007;

long long Euler(long long n) {
long long ans = n;
for(long long i = 2; i * i <= n; ++i) {
if(n % i == 0) {
ans = ans - ans / i;
while(n % i == 0) {
n /= i;
}
}
}
if(n > 1) ans = ans - ans / n;
return ans;
}

int main() {
long long n, k;
while(scanf("%lld %lld", &n, &k) != EOF) {
if(k == 2 || n == 1) {
puts("1");
} else if(k > 2) {
puts("0");
} else {
long long ans = 0;
for(long long i = 1; i * i <= n; ++i) {
if(n % i == 0) {
if(i * i == n) {
ans += Euler(n / i) * Euler(i);
}  else {
ans += 2 * Euler(n / i) * Euler(i);
}
ans %= MOD;
}
}
printf("%lld\n", ans);
}
}
return 0;
}
展开全文
• ## kmp1-HDU1711 HDU1686 HDU2087 HDU3746

千次阅读 多人点赞 2018-09-07 10:34:59
HDU 1711 kmp模板题 http://acm.hdu.edu.cn/showproblem.php?pid=1711 #include&lt;stdio.h&gt; #include&lt;string.h&gt; #define N 1000005 int s[N]; int p[N]; int next[N]; int m,n; void ...
HDU 1711 kmp模板题

http://acm.hdu.edu.cn/showproblem.php?pid=1711

#include<stdio.h>
#include<string.h>
#define N 1000005
int s[N];
int p[N];
int next[N];
int m,n;
void getnext(){
int j=0,k=-1;
next[0]=-1;
while(j<m){
if(k==-1||p[j]==p[k]){
j++;
k++;
next[j]=k;
}
else
k=next[k];
}
}
int kmp(){
int i=0,j=0;
getnext();
while(i<n){
if(j==-1||s[i]==p[j]){
i++;
j++;
}
else
j=next[j];
if(j==m)
return i;
}
return -1;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&s[i]);
for(int i=0;i<m;i++)
scanf("%d",&p[i]);
if(kmp()==-1)
printf("-1\n");
else
printf("%d\n",kmp()-m+1);
}
return 0;
}


HDU1686

http://acm.hdu.edu.cn/showproblem.php?pid=1686

题意就是，给你一个字符串A，一个字符串B，求A在B中总共出现了几次，注意，重复的也算。

稍微改动即可。

HDU 2087 剪花布条(KMP:贪心)

http://acm.hdu.edu.cn/showproblem.php?pid=2087

直接用KMP算法,用T模式串去匹配S主串即可，但是当匹配成功的时候要看看当前匹配点离上一个匹配点是不是距离差>=T的长度。

贪心，从左向右依次选取即可，证明略。

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=1000+100;
char S[MAXN],T[MAXN];
int next[MAXN];
int n,m;
int cnt,last;
void getFail()
{
next[0]=next[1]=0;
for(int i=1;i<m;i++)
{
int j=next[i];
while(j && T[i]!=T[j]) j=next[j];
next[i+1] = (T[i]==T[j])?j+1:0;
}
}
void KMP()
{
n=strlen(S);
m=strlen(T);
getFail();
int j=0;
for(int i=0;i<n;i++)
{
while(j && S[i]!=T[j]) j=next[j];
if(S[i]==T[j]) j++;
if(j==m)
{
if(cnt==0)
{
cnt++;
last=i;//last指向匹配位置的末尾
}
else if(i-last>=m)
{
cnt++;
last=i;
}
}
}
}
int main()
{
while(scanf("%s",S)==1)
{
if(strcmp(S,"#")==0)
break;
scanf("%s",T);
cnt=0;
KMP();
printf("%d\n",cnt);
}
return 0;
}


HDU3746 next应用

http://acm.hdu.edu.cn/showproblem.php?pid=3746

逻辑就是找到最长相同前后缀再在后面加上那一段就找到了.

注意：用原始next，next数组存的是前缀和后缀的最大匹配值，

比如abcabca

改进前最后一个字符next[7]=4,表示的是前缀和后缀最大匹配是4，即abca和abca。

改进后的next[7]=-1。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100010

char s[N];
int nextval[N];
int len;

void getnext(const char *s)
{
int i = 0, j = -1;
nextval[0] = -1;
while(i != len)
{
if(j == -1 || s[i] == s[j])
nextval[++i] = ++j;
else
j = nextval[j];
}
}

int main()
{
int ncase;
scanf("%d", &ncase);
while(ncase--)
{
scanf("%s", s);
len = strlen(s);
getnext(s);
/*for(int i = 0; i <= len; ++i) //查看next数组的内容
cout<<nextval[i]<<" ";
cout<<endl;*/
length = len - nextval[len]; //循环节的长度
if(len != length && len % length == 0) //循环多次
printf("0\n");
else
{
add = length - nextval[len] % length; //取余的作用：abcab，去掉abc
}
}
return 0;
}



展开全文
• Catalan数（卡特兰数） HDU 2067 HDU 1023 HDU 1131

HDU 2067：
#include <bits/stdc++.h>

using namespace std;

long long catalan[42];

void Catalan(int n) {
catalan[0] = catalan[1] = 1;
for(int i = 2; i <= n; ++i) {
catalan[i] = 0;
for(int j = 0; j < i; ++j) {
catalan[i] += catalan[j] * catalan[i-j-1];
}
}
}

int main() {
int n, cas = 1;
Catalan(35);
while(scanf("%d", &n) != EOF) {
if(n == -1) break;
printf("%d %d %lld\n", cas++, n, 2 * catalan[n]);
}
return 0;
}HDU 1023：
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
static BigInteger[] catalan = new BigInteger[108];  // Objects must be initialized befor use
public void Catalan() {
catalan[0] = catalan[1] = BigInteger.ONE;
for(int i = 2; i <= 100; ++i) {
catalan[i] = BigInteger.ZERO;
for(int j = 0; j < i; ++j) {
}
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
Main obj = new Main();
obj.Catalan();
while(cin.hasNext()) {
int n;
n = cin.nextInt();
System.out.println(catalan[n]);
}
}
}


HDU  1131：
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
static BigInteger[] catalan = new BigInteger[108];
public void Catalan() {
catalan[0] = catalan[1] = BigInteger.ONE;
for(int i = 2; i <= 100; ++i) {
catalan[i] = BigInteger.ZERO;
for(int j = 0; j < i; ++j) {
}
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
Main obj = new Main();
obj.Catalan();
while(cin.hasNext()) {
int n;
n = cin.nextInt();
if(n == 0) {
break;
}
BigInteger pro = BigInteger.ONE;
for(long i = 2; i <= n; ++i) {
pro = pro.multiply(BigInteger.valueOf(i));
}
System.out.println(pro.multiply(catalan[n]));
}
}
}

展开全文
• 1. HDU1702 ACboy needs your help again! 简单的栈和队列 2. HDU1022 Train Problem I O1为火车进队的序列，问是否能以O2出队。读题时很容易进入误区，会以为严格按照O1进队，中间不会有任何火车出队。


1. HDU1702 ACboy needs your help again!

简单的栈和队列

2. HDU1022 Train Problem I

O1为火车进队的序列，问是否能以O2出队。读题时很容易进入误区，会以为严格按照O1进队，中间不会有任何火车出队。
例如数据5
12342 24321
Yes.
in
in
out
in
in
out
out
in
out
out
FINISH
火车入队顺序为12342，火车出队顺序为24321。队列中出队入队的顺序为1(in) - 2(in) - 2(out) - 3(in) - 4(in) - 4(out) - 3(out) - 2(in) - 2(out) - 1(out) 。

3. HDU1237 简单计算器

每次读入一个数n和一个符号ch，如果符号为 + 或 - 就 push(n)或push(-n)，如果符号为 * ，就先取出队头，然后push乘积，如果符号为 /，则push商。读取输入会有些麻烦。

4. HDU3328 Flipper
需要去记录纸牌的朝向，一个堆为一个栈。如果操作为R，则将从右数起第一个非空的栈，对其进行反转，然后push到其左边的栈中；如果操作为L，则将从左数起第一个非空的栈，对其进行反转，然后push到其右边的栈中。每次push，都需要把当前栈中的纸牌翻转。

5. HDU1873  看病要排队
优先队列很好解决，需要记录病人的编号ID，以优先级为第一关键字，编号为第二关键字排序，且一个为升序，一个为降序。

6. HDU1509  Windows Message Queue
同样要用优先队列和序号ID，也是以优先级为第一关键字，编号为第二关键字排序，且都同为降序或同为升序。

7. HDU1870  愚人节的礼物

直接放入队列，直到遇到礼物，然后就一直pop，pop的次数即为答案。

8. HDU1387  Team Queue

可以用一个set来存队伍信息，然后通过入队的号码来依次在队伍中找其所属的队伍编号，可以用set的find方法，如果找到就将其入队其队友的队列中，未找到则新建队列，可以用一个变量来记录队列的序号，新建队列时只需++。

题解详见：http://blog.csdn.net/vtfghs/article/details/74588459


展开全文
• HDU - 1029 题意：找出出现次数超过一半的数字 蠢思路：排序找中间 DP：扫一遍一个变量count记录解出现的次数，是当前解就++，否则--，count为负就换掉当前解。（解释：想象解全都挨在一起（前面），count先达到...
• ## hdu2111 Saving HDU

千次阅读 2018-04-12 08:03:52
Saving HDUTime Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 14789 Accepted Submission(s): 6631Problem Description话说上回讲到海东集团面临内外交困，...
• hdu1171 Big Event in HDU
• hdu 4505: 直接上代码，只需统计最高楼层，和在某一层有多少人! #include #include using namespace std; int t,n,a[20]; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); int i; for
• hdu ACM 1.2.6 hdu3361
• hdu ACM 1.2.7 hdu 2629
• hdu ACM 1.2.4 hdu2399
• ACM hdu 1.2.1 hdu 1049
• hdu ACM 1.25 hdu3188
• hdu ACM 1.3.4 hdu2561
• hdu ACM 1.2.3 hdu1064
• Problem Description ...Hdu Girls' Day is a traditional activity in Hdu. Girls in Hdu participate in the activity and show their talent and skill. The girls who win in the activity will become the Hdu'
• ## HDU5944

千次阅读 2017-05-12 16:15:50
HDU5944
• hdu 2014
• hdu 2013
• HDU 2000
• If you ask one student of HDU “who is the superstar in HDU now?” ,the answer must be “HDU CakeMan” .He sells little cakes in the gate of the HDU students’ dormitory every day .As he says “做人要...
• HDU_STEPS 6.1 最小生成树   6.1.1 HDU 1102 Constructing Roads 裸的最小生成树 6.1.2 HDU 1162 Eddy's picture 最小生成树,每两点直接连线建图 6.1.3 HDU 1232 畅通工程 用并查集将图分块,然后修N-1条路即可 ...
• 7.1.1 HDU2108 Shape of HDU 判断凸多边形，每连续三个点之间求叉积判断即可 7.1.2 HDU1086 You can Solve a Geometry Problem too 判断线段相交，模板题，参考吉大模板 7.1.3 HDU1115 Lifting the Stone ...
• 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2104 思路分析：m和n互质即可。与hdu1222相同 http://acm.hdu.edu.cn/showproblem.php?pid=1222 转载于:...
• STEPS7.2 数论 （ 数论一直很烂啊。。。）   7.2.1 HDU2824 The Euler function 欧拉函数，打表sum[i]表示phi[1]到phi[i]的和，最后输出sum[b]-sum[a-1] ...7.2.2 HDU1787 GCD Again ...7.2.3 HDU1757 A Si
• hdu5984 Pocky
• hdu1864 https://www.cnblogs.com/zhangmingcheng/p/3887416.html
• HDU各种考试题题解浙大计算机研究生复试上机考试-2005年HDU1228 A + B【map】 - 海岛Blog - CSDN博客HDU1231 最大连续子序列【最大子段和+DP】_算法,动态规划_海岛Blog-CSDN博客HDU1232 畅通工程【并查集】_Java_...
• hdu ACM 1.2.8 1219

...