ACM数论解题报告集合
Hdu 4143 y^2 = n +x^2
A Simple Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1650 Accepted Submission(s): 424
Problem Description
For a given positive integer n, please find the smallest positive integer x that we can find an integer y such that y^2 = n +x^2.
Input
The first line is an integer T, which is the the number of cases.
Then T line followed each containing an integer n (1<=n <= 10^9).
Output
For each integer n, please print output the x in a single line, if x does not exit , print -1 instead.
#include
#include
int main()
{
int i,t,n,x,flag;
scanf("%d",&t);
while(t--)
{
flag=0;
scanf("%d",&n);
i=sqrt(n);//n的平方根
for(i;i>=1;i--)
{
if(n%i==0&&(n/i-i)%2==0&&n/i!=i)
{
x=(n/i-i)/2;
printf("%d\n",x);
flag=1;
break;
}
}
if(flag==0) printf("-1\n");
}
return 0;
}
/*一开时超时是百分百的事不过要敢于写出超时的（在时间还充裕的情况下）
后来一直不知道真么做。对于这种类型的题目要密切结合式子的特点把2层循环变成一层
n=（x+y）*(x-y) 让i=x-y n/i做x+y x=(n/i-i)/2;
然后找出各种条件限制满足则可求出结果
由于程序有可能出现n/i=i的情况但是题目中题意告诉我们不可能所以千万要排除这种情况
后来在这个地方也错了几次
*/
另外此题也可用欧几里得去做
hdu数论之Leftmost Digit
题目大意是输入N，求N^N的最高位数字。1<=N<=1,000,000,000
估计大家看到N的范围就没想法了。确实N的数字太大，如果想算出结果，即使不溢出也会超时。
这题我纠结了很久。在同学的提示下ac了。
题目是这样转化的。
首先用科学计数法来表示 N^N = a*10^x; 比如N = 3; 3^3 = 2.7 * 10^1;
我们要求的最右边的数字就是(int)a，即a的整数部分;
OK, 然后两边同时取以10为底的对数 lg(N^N) = lg(a*10^x) ;
化简 N*lg(N) = lg(a) + x;
继续化 N*lg(N) - x = lg(a)
a = 10^(N*lg(N) - x);
现在就只有x是未知的了，如果能用n来表示x的话，这题就解出来了。
又因为，x是N^N的位数。比如 N^N = 1200 ==> x = 3; 实际上就是 x 就是 lg(N^N) 向下取整数，表示为[lg(N^N)]
ok a = 10^(N*lg(N) - [lg(N^N)]); 然后(int)a 就是答案了。
#include
#include
int main()
{
int t;
long long ans;
double k,n;
scanf("%d",&t);
while(t--)
{
scanf("%lf",&n);
k=n*log10(n);
k=k-(long long)k;
ans=(long long)pow(10.0,k);
printf("%lld\n",ans);
}
return 0;
}
注意最好让log中的数都是double型
另外遇到 n的n次方这种类型要第一时间考虑到log
另外 t绝对不能为long long 这样会超时
所以以后对于决定case的数要用int输入
最小差值
给出一个整数数组a1, a2, …, an，求数组中两个数的最小差值。即在数组中找ai 和aj ，使得ai - aj 的值最小，并且i < j。
Input
输入的第一行是一个整数T，表示有T组数据。1 <= T <= 50。
每组数据第一行输入一个整数n,第二行输入n个整数：a1,a2…,an。
1 <= T <= 50,
2 <= n <= 1000000, -1000000000 <= ai <= 1000000000。
Output
对于每组数据，输出一行，即最小差值。
Sample Input
3
2
1 1
3
3 2 0
4
6 8 -4 10
Sample Output
1
-14
#include
int a[1000005];
int main()
{
int t,i,j,min,ans,n,mid;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i { scanf("%d",&a[i]); } min=a[0]; ans=1000000000; for(i=1;i { mid=min-a[i]; min=min ans=mid } printf("%d\n",ans); } return 0; } /*一开始在这个题上面扣了好几个小时好郁闷暴力百分百超时居然还想到了用快排 不过很遗憾排了没有用因为这题和快排扯不上边哎究其原因：都怪自己没有好好分析 题意拿题就做没有真正分析透题的本质对于此题就是求最小值那只要被减数越小就行了呗*/ 同学的做法很给力啊 ：1002 对原始数据处理下，前一个数减后一个数存到数组里，然后求最小连续子串和。 #include __int64 s[1000005],st[1000005]; int main() { int t; int n,i; __int64 sum,sum1; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i scanf("%I64d",&s[i]); for(i=0;i st[i] = s[i] - s[i+1]; sum = sum1 = st[0]; for(i=1;i { if(sum1 + st[i] > st[i]) { if(st[i] < sum1) { sum1 = st[i]; if(sum1 < sum) sum = sum1; } } else { sum1 += st[i]; if(sum1 < sum) sum = sum1; } } printf("%I64d\n",sum); } return 0; } Hdu 1077 已知半径以及圆上2点求圆心 /*题目大意： 给出一些点坐标，问有一个半径为1的圆，一次最多能圈多小个点。 给定两个点，如里它们的距离大于直径，不必考虑，否则，认为这两个点在某一圆上，计算出圆心坐标， 依次遍历顶点，记录在这个圆里面的点，这个值就是我们要进行判定的值。。。 */ /*对于本题我是狗屁不懂但是有一个很重要的东西 就是已知半径以及圆上2点求圆心 只要会用这个求圆心的方法即可*/ #include #include const static double eps = 1e-6; struct Point { double x,y; }; double distancess(Point a,Point b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } Point look_center(Point a,Point b) //已知半径以及圆上2点求圆心代码：a，b是圆上点 { Point aa,bb,mid; aa.x = b.x-a.x; aa.y = b.y-a.y; mid.x = (a.x+b.x)/2.0; mid.y = (a.y+b.y)/2.0; double dist = distancess(a,mid); double c = sqrt(1.0-dist); //1.0是半径套用代码时要根据题意改变 // if(fabs(aa.y) // { // bb.x = mid.x; // bb.y = mid.y+c; //这几句nop掉的话加上可以减少时间不加也能过不知道是干嘛的 // } // else // { double ang = atan(-aa.x/aa.y); bb.x = mid.x + c*cos(ang); bb.y = mid.y + c*sin(ang); // } return bb;//用结构体变量bb存储圆心的坐标并返回 } int main() { int test; Point p[305],a; int n; scanf("%d",&test); while(test--) { scanf("%d",&n); for(int i=0; i scanf("%lf%lf",&p[i].x,&p[i].y); int ans = 1; int temp = 0; for(i =0;i for(int j=i+1;j { if(distancess(p[i],p[j])>4) continue; a = look_center(p[i],p[j]); temp = 0; for(int k=0;k { if(distancess(a,p[k])<=1.000001) temp++; } if(ans } printf("%d\n",ans); } return 0; } Hdu1124 题意：N阶乘有多少个尾0？(1 <= N <= 1000000000) /*容易知道5以后的阶乘都是偶数那么产生新的0 只有当偶数*5 那么对于25 可以分为 5*5 那么 25的阶乘等于24的阶乘*5*5 会多出2个0 125的阶乘等于124的阶乘*125 会多出3个0 所以只要看n里有多少个5的倍数多少个25的倍数。。。。。。 （由于*25的产生的2个0 可以在计算5的倍数时去掉一个 25对应相当于1个0 同理125 也相当于一个0 ） 那么结果为n/5+n/25+n/125+......*/ #include int main() { int n,ans,i,k,cnt,num; while(scanf("%d",&k)!=EOF) { while(k--) { scanf("%d",&n); ans=0; num=1; while(num<=n) { num*=5; ans+=n/num; } printf("%d\n",ans); } } return 0; } hdu 1568 Fib数通项公式求某个数的前4位 Fibonacci Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2076 Accepted Submission(s): 959 Problem Description 2007年到来了。经过2006年一年的修炼，数学神童zouyu终于把0到100000000的Fibonacci数列(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i>=2))的值全部给背了下来。 接下来，CodeStar决定要考考他，于是每问他一个数字，他就要把答案说出来，不过有的数字太长了。所以规定超过4位的只要说出前4位就可以了，可是CodeStar自己又记不住。于是他决定编写一个程序来测验zouyu说的是否正确。 Input 输入若干数字n(0 <= n <= 100000000)，每个数字一行。读到文件尾。 Output 输出f[n]的前4个数字（若不足4个数字，就全部输出）。 首先必须知道fib那次数列的通项公式为 对通项公式求log后 之后要知道 对数的性质,loga(b^c)=c*loga(b),loga(b*c)=loga(b)+loga(c); 假设给出10234432,那么 log10(10234432)=log10(1.0234432*10^7)=log10(1.0234432)+7; log10(1.0234432)就是log10(10234432)的小数部分. log10(1.0234432)=0.010063744 10^0.010063744=1.023443198 那么要取几位就很明显了吧~ 先取对数(对10取),然后得到结果的小数部分bit,pow(10.0,bit)以后如果答案还是<1000那么 就一直乘10。 注意偶先处理了0~20项是为了方便处理~ #include #include #include int a[25]; int main() { int i,n; double num; a[0]=0;a[1]=1; for(i=2;i<21;i++) a[i]=a[i-1]+a[i-2]; while(scanf("%d",&n)!=EOF) { if(n<=20) { printf("%d\n",a[n]); continue; } else { num=-0.5*log(5.0)/log(10.0)+((double)n)*log((sqrt(5.0)+1.0)/2.0)/log(10.0); num-=int(num); num=pow(10.0,num); while(num<1000) num*=10; printf("%d\n",(int)num); } } return 0; } n是否能被一个含有因子是一个平方数的数整出 能输出no 不能输出yes /*一个数n能被一个数的平方整除那么这个数一定能被一个质数的平方整出 如果能被一个偶数的平方整出由于偶数=2*x 一定含有质数2 故能被质素2的平方整出 假如一个数能被一个奇数的平方整除奇数=质数*x 故能被质素的平方整出 对于本题数据较大可以做如下处理 如果n>10^6 1 求出10^6内的所有质数看n是否可以分解成这些质数某个的平方如果可以输出No 2 数据最大为10^18 当那么最多存在一个数x使得x*x整出n 因为n*n*n大于10^18 故对其开方如果能开放则输出No 思维扩展： 对于一个平方数一定可以分解成某个质数的平方*某些质数 */ #include #include #include int vis[1000000+5]; int prime[79000]; int cnt[79000+5]; int c; void get_prime() { int i,j,n,m; c=0; n=1000000; m=(int)sqrt(n+0.5); memset(vis,0,sizeof(vis)); for(i=2;i<=m;i++) if(!vis[i]) { for(j=i*i;j<=n;j+=i) vis[j]=1; } for(i=2;i<=n;i++) if(!vis[i]) prime[c++]=i; } #include int main() { int i,j,cas,flag,k; __int64 n,m; double num; get_prime(); scanf("%d",&cas); for(k=1;k<=cas;k++) { scanf("%I64d",&n); memset(cnt,0,sizeof(cnt)); flag=0; for(j=0;j { m=n; while(m%prime[j]==0) { m/=prime[j]; cnt[j]++; if(cnt[j]>=2) {flag=1;break;} } if(flag) break; } if(n>1000000) { num=sqrt((double)n);//这里要注意必须要加double 否则编译错误 if(floor(num+0.5)==num) flag=1; } if(flag) printf("Case %d: No\n",k); else printf("Case %d: Yes\n",k); } return 0; } 一个迷迷糊糊的题目 f(n) Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 165 Accepted Submission(s): 92 Problem Description This time I need you to calculate the f(n) . (3<=n<=1000000) f(n)= Gcd(3)+Gcd(4)+…+Gcd(i)+…+Gcd(n). Gcd(n)=gcd(C[n][1],C[n][2],……,C[n][n-1]) C[n][k] means the number of way to choose k things from n some things. gcd(a,b) means the greatest common divisor of a and b. The output consists of one line with one integer f(n). 3 26983 Sample Output 3 37556486 /*通过打表找GCD的规律，规律如下： GCD(n)，当n只有一个质因子的时候GCD(n)不会为1。即质因子数大于等于2 的时候 GCD(n)=1 此时GCD等于n的这个唯一的质因子。 任何一个数都能分解成质因数的次方相乘 */ #include #include #include __int64 prime[100000],c; __int64 vis[1000000+10]; __int64 sum[1000000+10]; void get_prime() { __int64 i,j,n=1000000,m; c=0; m=(__int64)sqrt(n+0.5); memset(vis,0,sizeof(vis)); for(i=2;i<=m;i++) if(!vis[i]) { for(j=i*i;j<=n;j+=i) vis[j]=1; } for(j=2;j<=n;j++) if(!vis[j]) prime[c++]=j; } __int64 get(__int64 n) { __int64 i,k,cnt=0; for(i=0;prime[i]*prime[i]<=n&&i { if(n%prime[i]==0) { n=n/prime[i]; while(n%prime[i]==0) n=n/prime[i]; cnt++; k=prime[i]; } if(cnt>=2) return 1;//含有2个质因子则为1 } if(n>1) //大于1说明还存在一个质因子这里说实话我也不懂为什么 { cnt++; k=n; } if(cnt>=2) return 1; else return k; } int main() { __int64 i,n; sum[3]=3; get_prime(); for(i=4;i<=1000000;i++) if(vis[i])//不是质数（素数） sum[i]=sum[i-1]+get(i); else sum[i]=sum[i-1]+i;//是质数只有一个质因子就是其本身 while(scanf("%I64d",&n)!=EOF) { printf("%I64d\n",sum[n]); } return 0; } Largest prime factor //求一个数的最大素因子是第几个素数,打表 #include #include #define N 1000000 int a[N]; int main() { int n=0,i,t,j; memset(a,0,sizeof(a)); for(i=2;i<=N;i++)//对当前数的每个数的倍数进行赋值素数编号可以覆盖哦因为要覆盖为最大因子 { if(a[i]==0) { n++;//素数i的位置 for(j=i;j<=N;j+=i)//构造出j的暂时最大素数因子的位置 a[j]=n; } } while(scanf("%d",&i)!=EOF) { printf("%d\n",a[i]); } return 0; } 如果用打印素数表后然后分解质因子找到最大质因子输出对应位置超时 hdu 3501 数论与n不互质的数的和若N个整数的最大公因数是1，则称这N个整数互质。 题意： 输入n 计算比n小的数中和n不互质的数的和%1000000007 /* if gcd(n,i)==1 then gcd(n,n-i)==1 所以那么对于n有phi(n)(欧拉函数)个小于n的数与n互质 由上面的公式可以知道其中一个若为i则存在一个为n-i 那么2者之和为n 这样的一共有phi(n)/2对 故与n互质的所有数的和为n*phi(n)/2 那么与n不互质的数就是(1+n-1)*(n-1)/2-n*phi(n)/2 */ #include #include #define mod 1000000007 __int64 get_phi(__int64 x)// 就是公式 { __int64 i, res=x; for (i = 2; i <(__int64)sqrt(x * 1.0) + 1; i++) if(x%i==0) { res = res / (__int64)i * (i - 1); while (x % i == 0) x /= i; // 保证i一定是素数 } if (x > 1) res = res / (__int64)x * (x - 1);//这里小心别溢出了 return res; } int main() { __int64 n,ans; while(scanf("%I64d",&n)!=EOF) { if(!n) break; ans=((__int64)(1+n-1)*(n-1)/2-(__int64)n*get_phi(n)/2)%mod;//不能先除2再乘 printf("%I64d\n",ans%mod); } return 0; } /* 题意：输入case个数 输入n m 表示问从1到n的数与n的公约数大于m的数的个数 (2<=N<=1000000000, 1<=M<=N), 思路： 首先找出n的所有大于m的公约数k 然后求出每个对应的n/k的phi(欧拉函数) 即小于n/k的数与n/k互质的个数 那么这些数与n/k互质且小于n/k 那么这些与n/k互质的数乘以k之后那么就变成了与n公约数为k的数(k>m) 把所有的phi(n/k)相加即是答案当然这思路是参考人家的呜呜。。。。。。。。。。。。。 另外本人有个小疑问：怎么保证这些数没有重复啊比如k1 k2 均为n的约数那么如果不同的2个数分别与n/k1 n/k2互质 那么分别乘以k1,k2后为一个数怎么办不是重复了吗？请高手给留个言证明下为什么不会重复 */ #include #include int num[40000],cnt2; int phi(int x)// 就是公式 { int i, res=x; for (i = 2; i <(int)sqrt(x * 1.0) + 1; i++) if(x%i==0) { res = res /i * (i - 1); while (x % i == 0) x /= i; // 保证i一定是素数 } if (x > 1) res = res /x * (x - 1);//这里小心别溢出了 return res; } int main() { int i,Cas; scanf("%d",&Cas); while(Cas--) { int n,m; scanf("%d%d",&n,&m); cnt2=0; int s=0; for(i=1;i*i if(n%i==0) { // if(i>=m) // s+=phi(i); // if(n/i>=m) // s+=phi(n/i); if(i>=m) num[cnt2++]=i; if(n/i>=m) num[cnt2++]=n/i; } if(i*i==n&&n%i==0&&i>=m) num[cnt2++]=i; for(i=0;i s+=phi(n/num[i]); printf("%d\n",s); } return 0; } hdu 3816 To Be NUMBER ONE 一道数论主要是思路 题意 分别用3到18个数的倒数相加等于1 并且每个数要求小于等于个数+1的平方 比如用3个数 那么要找3个数满足这三个数小于等于（3+1）*（3+1) 且倒数之和为1 思路： 一个倒数可以分解问2个数的倒数之和 1/n= 1/(a*b)=1/a*(a+b) + 1/b*(a+b) 故在已知上层的情况下可以直接将上一层的数分解为2个数以此类推即可 手算直接将结果写进代码即可 hdu 1695 综合数论欧拉函数分解质因子容斥原理打印素数表帅呆了的一个题目详解 /* 题目大意： 给你a, b, c, d, k; 找出这样的一队x, y，使得gcd(x , y) = k, 并且x ∈[1, b], y ∈[1, d], 问有多少对符合要求的(x, y)。 ------------------------------------------------------------------------------ 思路: gcd(x, y) == k 说明x,y都能被k整除, 但是能被k整除的未必gcd=k , 必须还要满足互质关系. 问题就转化为了求1~a/k 和1~b/k间互质对数的问题可以把a设置为小的那个数, 那么以y>x来保持唯一性(题目要求, 比如[1,3] =[3,1] ) 接下来份两种情况: 1. y <= a , 那么对数就是1~a的欧拉函数的累计和(容易想到) 2. y >= a , 这个时候欧拉函数不能用了,怎么做?可以用容斥原理,把y与1~a互质对数问题转换为y的质数因子在1~a范围内能整除的个数(质数分解和容斥关系)， */ #include #include #include #include #include using namespace std; const int N = 100005; typedef long long LL; #define maxn 100005 LL phi[N]; vector int vis[1000000+5],c; LL prime[79000]; void get_prime() //打印素数表模板 { int i,j,n,m; c=0; n=1000000; m=(int)sqrt(n+0.5); memset(vis,0,sizeof(vis)); for(i=2;i<=m;i++) if(!vis[i]) { for(j=i*i;j<=n;j+=i) vis[j]=1; } for(i=2;i<=n;i++) if(!vis[i]) prime[c++]=i; } void get_PHI() //模板得到1->n之内与n互质的数的个数存入phi[n] { int i,j; for (i = 1; i <= maxn; i++) phi[i] = i; for (i = 2; i <= maxn; i += 2) phi[i] /= 2; for (i = 3; i <= maxn; i += 2) if(phi[i] == i) { for (j = i; j <= maxn; j += i) phi[j] = phi[j] / i * (i - 1); } } void init() //求每一个数的质因数，vector储存 { LL i, j, k; for(i = 1; i < N; i++)//求n的质因数也是模板 { k = i; for(j = 0; prime[j]*prime[j] <= k; j++) { if(k%prime[j] == 0) { link[i].push_back(prime[j]); while(k%prime[j] == 0) k /= prime[j]; } if(k == 1) break; } if(k > 1) link[i].push_back(k); } } LL make_ans(LL num,LL n)//1到num中的所有数与n的m个质因子不互质的数的个数注意是不互质哦容斥原理 { LL ans=0,tmp,i,j,flag; for(i=1;i<(LL)(1< { //用二进制来1,0来表示第几个素因子是否被用到,如m=3，三个因子是2,3,5，则i=3时二进制是011，表示第2、3个因子被用到 tmp=1,flag=0; for(j=0;j if(i&((LL)(1< flag++,tmp*=link[n][j];//第j个质因子link[n][j] if(flag&1)//容斥原理，奇加偶减 ans+=num/tmp; else ans-=num/tmp; return ans; } int main() { LL i, a, b, c, d, k, sum, t, zz = 1;//longlong型的数据可以用%I64d 来输入输出get_prime(); get_PHI(); init(); scanf("%I64d", &t); while(t--) { scanf("%I64d %I64d %I64d %I64d %I64d", &a, &b, &c, &d, &k); if(k == 0 || k > b || k > d) { printf("Case %I64d: 0\n", zz++); continue; } if(b > d) swap(b, d);//保持d较大 b /= k; d /= k; sum = 0; for(i = 1; i <= b; i++) { sum += phi[i]; } for(i = b+1; i <= d; i++) { sum += b - make_ans(b, i); } printf("Case %I64d: %I64d\n", zz++, sum); } return 0; } hdu 4398 多校联合赛第九场X mod f(x) 数论 题意： 输入n m 从n到m算出满足x%f(x)的数的个数 POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: poj 1061 青蛙的约会 这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。内容如下： 对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值，这个就是线性同余方程。符号说明： mod表示：取模运算 ax≡b(mod m)表示：(ax - b) mod m = 0，即同余 gcd(a,b)表示：a和b的最大公约数 求解ax≡b(mod n)的原理：对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法如下： 第一个问题：求解gcd(a,b) 定理一：gcd(a,b) = gcd(b,a mod b) 欧几里德算法 int Euclid(int a,int b) { if(b == 0) return a; else return Euclid(b,mod(a,b)); } 附：取模运算 int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } 第二个问题：求解ax + by = gcd(a,b) 定理二：ax + by = gcd(a,b)= gcd(b,a mod b) = b * x' + (a mod b) * y' = b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 则：x = y' y = x' - a / b * y' 以上内容转自https://www.sodocs.net/doc/068073421.html,/redcastle/blog/item/934b232dbc40d336349bf7e4.html 1、POJ 2249 Binomial Showdown 组合数学。 高精度，也可把分子分母的数组进行两两约分 #include 有一个溢出问题；比如64位全是p的序列，那么max会溢出，值为-1；同理min在全是n 时也会溢出，为1；显然是max>=0,min<=1,溢出时产生异常，依次可以判断； ②是否是最大限和最小限之间的数都能表示呢？ 都可以，而且能够表示的数是2^k个，这个原始2进制是一样的；因为每个位上要么是0，要么是1，而且每个位上的权重唯一的，不能通过其他位的01组合获得；最后，我们就可以仿照原始二进制来算在类2进制下的表示；不断求N的二进制最后一位和右移；如果取余是1，则该位上一定是1，如果该位对于字母为‘n’，则高位应该再加1；这里对2取余可能会出错，因为对于负数，补码的表示，最后一位一定是和原码一样的每次的右移后(有时需先加1）补码表示正好符合要求（可找实例验证）； #include 1、公约数和公倍数 https://www.sodocs.net/doc/068073421.html,/JudgeOnline/problem.php?pid=40 这道题目是非常基础的题目，在学习了欧几里德算法之后，应该很好就能做的出来了。注意两个数的最小公倍数和最大公约数之间有关系为： a*b=gcd(a,b)*lcm(a,b); 代码如下： #include ?????≡≡≡)33(mod ) 28(mod )23(mod d n e n p n 那么找到k1、k2、k3满足： k1：k1%23==0&&k1%28==0&&k1%33==1 k2：k2%33==0&&k2%28==0&&k2%23==1 k3：k3%33==0&&k3%23==0&&k3%28==1 则n=k2*p+k3*e+k1*i+k*21252； 代码如下： #include 数论50题 1．由1，3，4，5，7，8这六个数字所组成的六位数中，能被11整除的最大的数是多少？ 【分析】各位数字和为1+3+4+5+7+8=28 所以偶数位和奇数位上数字和均为14 为了使得该数最大，首位必须是8，第2位是7，14-8=6 那么第3位一定是5，第5位为1 该数最大为875413。 2．请用1，2，5，7，8，9这六个数字（每个数字至多用一次）来组成一个五位数，使得它能被75整除，并求出这样的五位数有几个？ 【分析】75=3×25 若被3整除，则各位数字和是3的倍数，1+2+5+7+8+9=32 所以应该去掉一个被3除余2的，因此要么去掉2要么去掉8 先任给一个去掉8的，17925即满足要求 1）若去掉8 则末2位要么是25要么是75，前3位则任意排，有3！=6种排法 因此若去掉8则有2*6=12个满足要求的数 2）若去掉2 则末2位只能是75，前3位任意排，有6种排法 所以有6个满足要求 综上所述，满足要求的五位数有18个。 3．已知道六位数20□279是13的倍数，求□中的数字是几？ 【分析】根据被13整除的判别方法，用末三位减去前面的部分得到一个两位数，十位是7，个位是（9-□），它应该是13的倍数，因为13|78,所以9-□=8 □中的数字是1 4．某自然数，它可以表示成9个连续自然数的和，又可以表示成10个连续自然数的和，还可以表示成11个连续自然数的和，那么符合以上条件的最小自然数是？（2005全国小学数学奥赛） 【分析】可以表示成连续9个自然数的和说明该数能被9整除，可以表示成连续10个自然数的和说明该数能被5整除，可表示成连续11个自然数的和说明该数能被11整除 因此该数是[9,5,11]=495，因此符合条件的最小自然数是495。 5．一次考试中，某班同学有考了优秀，考了良好，考了及格，剩下的人不及格，已知该班同学的人数不超过50，求有多少人不及格？ 【分析】乍一看这应该是一个分数应用题，但实际上用到的却是数论的知识，由于人数必须是整数，所以该班同学的人数必须同时是2，3，7的倍数，也就是42的倍数，又因为人数不超过50，所以只能是42人，因此不及格的人数为（1---）×42=1人 6．（1）从1到3998这3998个自然数中，有多少个能被4整除？ （2）从1到3998这3998个自然数中，有多少个数的各位数字之和能被4整除？ （第14届迎春杯考题） 【分析】（1）3998/4=999….6所以1-3998中有996个能被4整除的 （2）考虑数字和，如果一个一个找规律我们会发现规律是不存在的 因此我们考虑分组的方法 我们补充2个数，0000和3999，此外所有的一位两位三位数都在前面加上0补足4位 然后对这4000个数做如下分组 断断续续的学习数论已经有一段时间了，学得也很杂，现在进行一些简单的回顾和总结。学过的东西不能忘啊。。。 1、本原勾股数： 概念：一个三元组(a,b,c)，其中a,b,c没有公因数而且满足：a^2+b^2=c^2 首先，这种本原勾股数的个数是无限的，而且构造的条件满足： a=s*t,b=(s^2-t^2)/2,c=(s^2+t^2)/2 其中s>t>=1是任意没有公因数的奇数！ 由以上概念就可以导出任意一个本原勾股数组。 2、素数计数（素数定理） 令π(x)为1到x中素数的个数 19世纪最高的数论成就就是以下这个玩意儿： lim(x->∞){π(x)/(x/ln(x))}=1 数论最高成就，最高成就！！！有木有！！！ 3、哥德巴赫猜想(1+1) 一个大偶数(>=4)必然可以拆分为两个素数的和，虽然目前还没有人能够从理论上进行证明，不过我根据科学家们利用计算机运算的结果，如果有一个偶数不能进行拆分，那么这个偶数至少是一个上百位的数！！ 所以在ACM的世界中（数据量往往只有2^63以下）哥德巴赫猜想是成立的！！所以拆分程序一定能够实现的 4、哥德巴赫猜想的推广 任意一个>=8的整数一定能够拆分为四个素数的和 证明： 先来说8=2+2+2+2，（四个最小素数的和）不能再找到比2小的素数了，所以当n小于8，就一定不可能拆分为四个素数的和！ 那么当n大于等于8，可以分情况讨论： （1）n&1==0(n为偶数)，那么n就一定可以拆分为两个偶数的和 那么根据哥德巴赫猜想，偶数可以拆分为两个素数的和，于是，n一定可以拆分为四个素数的和 （2）n&1==1(n为奇数)，n一定可以拆分为两个偶数+1 由于有一个素数又是偶数，2，那么奇数一定有如下拆分：2+3+素数+素数 得证。 ACM入门之新手入门 1.ACM国际大学生程序设计竞赛简介 1)背景与历史 1970年在美国T exasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。1977年，该项竞赛被分为两个级别：区域赛和总决赛，这便是现代ACM竞赛的开始。在亚洲、美国、欧洲、太平洋地区均设有区域赛点。1995至1996年，来自世界各地的一千多支s代表队参加了ACM区域竞赛。ACM大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。 2)竞赛组织 竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。参赛队应首先参加每年9月至11月在世界各地举行的“区域竞赛(Regional Contest)”。各区域竞赛得分最高的队伍自动进入第二年3月在美国举行的“总决赛(Final Contest)”，其它的高分队伍也有可能被邀请参加决赛。每个学校有一名教师主管队伍，称为“领队”(faculty advisor)，他负责选手的资格认定并指定或自己担任该队的教练(coach)。每支队伍最多由三名选手(contestant)组成，每个选手必须是正在主管学校攻读学位的学生。每支队伍最多允许有一名选手具有学士学位，已经参加两次决赛的选手不得再参加区域竞赛。 3)竞赛形式与评分办法 竞赛进行5个小时，一般有6~8道试题，由同队的三名选手使用同一台计算机协作完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。 程序运行不正确是指出现以下4种情况之一： (1)运行出错(run-time error)； (2)运行超时〔time-limit exceeded〕； (3)运行结果错误(wrong answer)； (4)运行结果输出格式错误(presentation error)。 竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用时的长短排名。总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时间是竞赛开始到提交被接受的时间加上该问题的罚时(每次提交通不过，罚时20分钟)。没有解决的问题不记时。美国英语为竞赛的工作语言。竞赛的所有书面材料(包括试题)将用美国英语写出，区域竞赛中可以使用其它语言。总决赛可以使用的程序设计语言包括PASCAL，C，C++及Java，也可以使用其它语言。具体的操作系统及语言版本各年有所不同。 4)竞赛奖励情况 总决赛前十名的队伍将得到高额奖学金：第一名奖金为12000美元，第二名奖金为 6000美元，第三名奖金为3000美元，第四名至第十名将各得到l500美元。除此之外还将承认北美冠军、欧洲冠军、南太平洋冠军及亚洲冠军。 2.ACM竞赛需要的知识 语言是最重要的基本功 无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当 ACM部分习题答案： A + B Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 100972 Accepted Submission(s): 33404 Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 # include -北大poj acm题目推荐50题 POJ == 北京大学ACM在线评测系统https://www.sodocs.net/doc/068073421.html,/JudgeOnline 1. 标记难和稍难的题目大家可以看看，思考一下，不做要求，当然有能力的同学可以直接切掉。 2. 标记为A and B 的题目是比较相似的题目，建议大家两个一起做，可以对比总结，且二者算作一个题目。 3. 列表中大约有70个题目。大家选做其中的50道，且每类题目有最低数量限制。 4. 这里不少题目在BUPT ACM FTP 上面都有代码，请大家合理利用资源。 5. 50个题目要求每个题目都要写总结，养成良好的习惯。 6. 这50道题的规定是我们的建议，如果大家有自己的想法请与我们Email 联系。 7. 建议使用C++ 的同学在POJ 上用G++ 提交。 8. 形成自己编写代码的风格，至少看上去美观，思路清晰(好的代码可以很清楚反映出解题思路)。 9. 这个列表的目的在于让大家对各个方面的算法有个了解，也许要求有些苛刻，教条，请大家谅解，这些是我们这些年的经验总结，所以也请 大家尊重我们的劳动成果。 10. 提交要求：一个总文件夹名为bupt0xx (即你的比赛帐号), 这个文件夹内有各个题目类别的子目录(文件夹)，将相应的解题报告放入对应 类别的文件夹。在本学期期末，小学期开始前，将该文件夹的压缩包发至buptacm@https://www.sodocs.net/doc/068073421.html,。 对于每个题目只要求一个POJxxxx.cpp 或POJxxxx.java (xxxx表示POJ该题题号) 的文件，注意不要加入整个project 。 11. 如果有同学很早做完了要求的题目，请尽快和我们联系，我们将指导下一步的训练。 下面是一个解题报告的范例： 例如：POJ1000.cpp 目录 数A01 敲七 (1) 数A02 三角形面积 (2) 数A03 3n+1数链问题 (3) 数A04 统计同成绩学生人数 (4) 数A05 分解素因子 (5) 数A06 亲和数 (6) 数B01 寒冰王座 (7) 数B02 整数对 (8) 数B03 麦森数 (9) 数B04 Feli的生日礼物 (10) 注：数表示本题属于初等数论，A表示简单，B表示稍难。 数A01 敲七 【问题描述】 输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）【数据输入】一个整数N。(N不大于30000) 【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。 【样例输入】 20 【样例输出】 7 14 17 数A02 三角形面积 【问题描述】 给出三角形的三个边长为a，b，c，根据海伦公式来计算三角形的面积： s = (a+b+c)/2； area = sqrt(s*(s-a)*(s-b)*(s-c)); 【数据输入】测试的数据有任意多组，每一组为一行。 每一行为三角形的三个边长为a，b，c； 【数据输出】输出每一个三角形的面积，两位小数。如果不是一个三角形，则输出错误提示信息：“Input error!” 【样例输入】 3 4 5 6 8 10 1 2 3 【样例输出】 6.00 24.00 Input error! 数A03 3n+1数链问题 【问题描述】 在计算机科学上，有很多类问题是无法解决的，我们称之为不可解决问题。然而，在很多情况我们并不知道哪一类问题可以解决，那一类问题不可解决。现在我们就有这样一个问题，问题如下： 1. 输入一个正整数n； 2. 把n显示出来； 3. 如果n=1则结束； 4. 如果n是奇数则n变为3n+1 ，否则n变为n/2； 5. 转入第2步。 例如对于输入的正整数22，应该有如下数列被显示出来： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 我们推测：对于任意一个正整数，经过以上算法最终会推到1。尽管这个算法很简单，但我们仍然无法确定我们的推断是否正确。不过好在我们有计算机，我们验证了对于小于1,000,000的正整数都满足以上推断。对于给定的正整数n，我们把显示出来的数的个数定义为n的链长，例如22的链长为16。 你的任务是编写一个程序，对于任意一对正整数i和j，给出i、j之间的最长链长，当然这个最长链长是由i、j之间的其中一个正整数产生的。我们这里的i、j之间即包括i也包括j。 【数据输入】输入文件只有一行，即为正整数i和j，i和j之间以空格隔开。0 < i ≤j < 10,000。 【数据输出】文件只能有一行，即为i、j之间的最长链长。 【样例输入】 1 10 【样例输出】 20 目录 目录 (1) 一．扩展的欧几里德和不定方程的解 (2) 二．中国同余定理 (3) 三．原根 (5) 四．积性函数 (6) 五．欧拉函数性质 (7) 六．线性求1-max的欧拉函数值 (9) 七．求单个欧拉函数，求最小的x(phi（n）%x==0),使得2^x =1(mod n) (10) 一．扩展的欧几里德和不定方程的解 解不定方程ax + by = n的步骤如下: (1)计算gcd(a, b). 若gcd(a, b)不能整除n，则方程无整数解；否则，在方程的两边同除以gcd(a, b)，得到新的不定方程a'x + b'y = n'，此时gcd(a', b') = 1 (2)求出不定方程a'x + b'y = 1的一组整数解x0, y0，则n'x0，n'y0是方程a'x + b'y = n'的一组整数解。 (3)根据扩展欧几里德定理，可得方程a'x + b'y = n'的所有整数解为： x = n'x0 + b't y = n'y0 - a't (t为整数) 这也就是方程ax + by = n的所有整数解 利用扩展的欧几里德算法，计算(a, b)和满足gcd = (a, b) = ax0 + by0的x0和y0，也就是求出了满足a'x0 + b'y0 = 1的一组整数解。因此可得： x = n/gcd * x0 + b/gcd * t y = n/gcd * y0 - a/gcd * t (t是整数) int extend_Euclid(int a, int b, int &x, int &y) { if (b == 0){ x = 1; y = 0; return a; } int gcd= extend_Euclid ( b, a % b, x, y ); int temp = x; x = y; y = temp - (a / b) * y; return gcd; } 第二讲——数的奇偶性 一、基本概念和知识 一、奇数和偶数 整数可以分成奇数和偶数两大类.能被2整除的数叫做偶数，不能被2整除的数叫做奇数。 偶数通常可以用2k（k为整数）表示，奇数则可以用2k+1（k为整数）表示。 特别注意，因为0能被2整除，所以0是偶数。 二、奇数与偶数的运算性质 性质1：偶数±偶数=偶数， 奇数±奇数=偶数。 性质2：偶数±奇数=奇数。 性质3：偶数个奇数相加得偶数。 性质4：奇数个奇数相加得奇数。 性质5：偶数×奇数=偶数， 奇数×奇数=奇数。 三、奇反偶同：搞清一件事情的初始状态，进行奇数次操作，会和起始状态相反，进行偶数次操作，会回到初始状态。 二、例题 例1 1+2+3+…+99的和是奇数？还是偶数？ 例2 能不能在下面的每个方框中，分别填入加号或减号，使等式成立1□2□3□4□5□6□7□8□9=10 例3 元旦前夕，同学们相互送贺年卡.每人只要接到对方贺年卡就一定回赠贺年卡，那么送了奇数张贺年卡的人数是奇数，还是偶数？ 为什么？ 例4 桌上有9只杯子，全部口朝上，每次将其中6只同时“翻转”.请说明：无论经过多少次这样的“翻转”，都不能使9只杯子全部 口朝下。 例5 某校六年级学生参加区数学竞赛，试题共40道，评分标准是：答对一题给3分，答错一题倒扣1分.某题不答给1分，请说明该校 六年级参赛学生得分总和一定是偶数。 例5 在中国象棋盘任意取定的一个位置上放置着一颗棋子“马”，按中国象棋的走法，当棋盘上没有其他棋子时，这只“马”跳了若 干步后回到原处，问：“马”所跳的步数是奇数还是偶数？ 例6 一个俱乐部里的成员只有两种人：一种是老实人，永远说真话； 一种是骗子，永远说假话。某天俱乐部的全体成员围坐成一圈， 每个老实人两旁都是骗子，每个骗子两旁都是老实人。外来一位 记者问俱乐部的成员张三：“俱乐部里共有多少成员？”张三答： ACM数论基础之扩展欧几里德算法 欧几里德算法概述： 欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： gcd函数就是用来求(a,b)的最大公约数的。 gcd函数的基本性质： gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|) 欧几里得算法的公式表述 gcd(a,b)=gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d | b , d |r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证 欧几里德算法的C++语言描述 intGcd(int a, int b) { if(b == 0) return a; returnGcd(b, a % b); } 当然你也可以写成迭代形式： intGcd(int a, int b) { while(b != 0) { int r = b; b = a % b; a = r; } return a; } 扩展欧几里德定理 对于不完全为0 的非负整数a，b，gcd（a，b）表示a，b 的最大公约数，必然存在整数对x，y ，使得gcd（a，b）=ax+by。 c++语言实现 #include 数论中的基础概念 1群、环、域概念 A1：加法的封闭性：如果a 和b 属于G ，则a+b 也属于G A2：加法结合律：对G 中的任意元素a,b,c,a+(b+c)=(a+b)+c A3：加法单位元：G 中存在一个元素0，使得对于G 中的任意元素a ，有a+0=0+a A4：加法逆元：对于G 中的任意元素a ，G 中一定存在一个元素a,使得 a+(-a)=(-a)+a=0 A5：加法交换律：对于G 中的任意元素a 和b ，有a+b=b+a M1：乘法的封闭性：如果a 和b 属于G ，则ab 也属于G M2：乘法结合律：对于G 中的任意元素a,b,c 有a(bc)=(ab)c M3：乘法分配了：对于G 中的任意元素a,b,c ，有a(b+c)=ab+ac 和(a+b)c=ac+bc M4：乘法交换律：对于G 中的任意元素a,b 有ab=ba M5：乘法单位元：对于G 中的任意元素a,在G 中存在一个元素1，使得a1=1a=a M6：无零因子：对于G 中的元素a,b ，若ab=0，则必有a=0或b=0 M7：乘法逆元：如果a 属于G ，且a 不为0,则G 中存在一个元素1-a ，使得 111==--a a aa 满足A1---A4称为群 满足A1---A5称为可交换群 满足A1---M3称为环 满足A1---M4称为可交换换 满足A1---M6称为整环 满足A1---M7称为域 2循环群：如果群中的每一个元素都是一个固定元素)(G a a ∈的幂k a （k 为整数）， 则称群G 是循环群。我们认为元素a 生成了群G ，或者说a 是群G 的 生成元。 循环群总是交换群 3模运算 )mod ()mod (n b n a =则称整数a 和b 是模n 同余的，可以表示为：)(mod n b a ≡ 若b 整除a 。则用符号：a |b 表示。其性质可表示如下： ①如果a|1,那么a=-1或1。 ②如果a|b ，且b|a ，那么a=b 或a=-b ③任何不等于零的数整除0 ④如果b|g 且b|h ，那么对任意整数m,n 都有b|（mg+nh ） ACM 题型算法分类 题目均来自 主流算法 搜索//回溯 DP（动态规划） 贪心 图论//Dijkstra、最小生成树、网络流 数论//解模线性方程 计算几何//凸壳、同等安置矩形的并的面积与周长组合数学//Polya定理 模拟 数据结构//并查集、堆 10.博弈论 1、排序 1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 1002（需要字符处理，排序用快排即可）1007（稳定的排序）2159（题意较难懂）223 1 2371（简单排序）2388（顺序统计算法）2418（二叉排序树） 2、搜索、回溯、遍历 1022 1111d 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 238 6 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501， 1650,1659,1664,1753,2078 ,2083,2303,2310,2329 简单1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426, 不易1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349, 推荐1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288, 2331, 2339, 2340,1979（和迷宫类似）1980（对剪枝要求较高） ACM常用算法及其相应的练习题 2007-12-03 23:48 OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3 094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串 (poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253)ACM经典算法及配套练习题
(2020年编辑)ACM必做50题的解题-数论
ACM必做50题——数学
ACM数论方面十道基础题目详解
数论50题
数论
ACM入门之新手入门
ACM部分练习题目答案
北大 poj acm题目推荐50题
step1-数论 程序设计基础题ACM
ACM数论模板
数论2—数的奇偶性
ACM数论基础之扩展欧几里德详细证明
数论中的基础概念
简便算法的题型 ACM 题型算法分类
ACM常用算法及其相应的练习题