1、 公约数和公倍数 acm.nyist.net/JudgeOnline/problem.php?pid=40 这道题目是非常基础的题目,在学习了欧几里德算法之后,应该很好就能做的出来了。注意 两个数的最小公倍数和最大公约数之间有关系为:a*b=gcd(a,b)*lcm(a,b); 代码如下: #include
using namespace std; inline intGcd(intm,int n) //求最大公约数 { if (m==0) return n; returnGcd(n%m,m); } int main() { intn,a,b,g; cin>>n; while(n--) { cin>>a>>b; g=Gcd(a,b); cout< 2、 Biorhythms acm.nyist.net/JudgeOnline/problem.php?pid=151 很经典的中国剩余问题。 题目大意是:人的体力、情绪和智力都是有周期的,分别是 23 天、28 天和 33 天。分别给 出你体力、情绪和智力最高值过后的天数 p、e、d,然后让你计算下一次三者同时达到最高 值的时间。 23) n ≡ p(mod
? ? 那么再次达到最高值时间为 n,则有: ? n ≡ e(mod 28) ? n ≡ d (mod 33) ?
那么找到 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 int main() { intn,a,b,c,t; while(scanf("%d%d%d%d",&;a,&;b,&;c,&;t),~a) { n=(5544*a+14421*b+1288*c)%21252-t; if(n<=0) n+=21252; printf("%d\n",n); } } 3、 韩信点兵
acm.nyist.net/JudgeOnline/problem.php?pid=34 这个题目也是很经典的中国剩余问题类的题目, 思路跟上面差不多这道题目因为数据范围很 小实际上暴力就可以过, 但是这个题目不失为练习中国剩余的很好题目, 所以建议大家用中 国剩余定理做一下。 直接给出代码: 暴力求解代码: #include main() { inta,b,c,n; scanf("%d%d%d",&;a,&;b,&;c); for(n=11;n<100;n++) if(n%3==a&;&;n%5==b&;&;n%7==c) printf("%d\n",n); } 中国剩余定理思路代码: #include int main() { inta,b,c,m; scanf("%d %d %d",&;a,&;b,&;c); m=(70*a+21*b+15*c)%105; printf("%d\n",m); return 0; } 4、 次方求模 acm.nyist.net/JudgeOnline/problem.php?pid=102 这个题目是要求出 a 的 b 次方对 c 取余的值。 显然我们不能求出 a^b 后再对 c 取余,a^b 可能是一个很大的数,而且这样做肯定很慢。那 么我们利用同余定理来解决这个问题。 当然最简单的我们会想到:a^b%c=((a^(b-1)%c)*(a%c))%c; 但是这样效率依然是很低的。 那么我们考虑一种叫做二分快速幂的思路。 关键改进就是:a^b%c=((a^(b/2)%c)* (a^(b/2)%c))%c 比如我们要算 3^25%4 的值,由于 25=1+8+16,那么我们就只需要知道 3^1,3^8,3^16 的值。 这样复杂度就从 O(n)降低为 O(log(n))了。 代码实现如下: #include using namespace std; int mod(intk,intx,int c) { int a=1; longlong r=k; while(x) { if(x&;1) a=(a*r)%c; r=((r%c)*(r%c))%c; x=x>>1; } return a; } int main() { intn,a,b,c; cin>>n; while(n--) { cin>>a>>b>>c; cout< 、 青蛙的约会
poj.org/problem?id=1061 这道题目用到了扩展欧几里德算法。 设过 s 步后两青蛙相遇,则必满足以下等式:(x+m*s)-(y+n*s)=k*l(k=0,1,2....) 稍微变一下形得:(n-m)*s+k*l=x-y 令 n-m=a,k=b,x-y=c,即 a*s+b*l=c 只要上式存在整数解,则两青蛙能相遇,否则不能。 这样问题就转化为了扩展欧几里德问题了。 代码如下: # include __int64 gcd(__int64 a,__int64 b) { if(b==0) return a; returngcd(b,a%b); } voidexgcd(__int64 a,__int64 b,__int64 &;m,__int64 &;n) { if(b==0) { m=1; n=0; return ; } exgcd(b,a%b,m,n); __int64 t; t=m; m=n; n=t-a/b*n; } int main() { __int64 x,y,m,n,l,a,b,c,k1,k2,r,t; while(scanf("%I64d%I64d%I64d%I64d%I64d",&;x,&;y,&;m,&;n,&;l)!=EOF) { a=n-m; b=l; c=x-y; r=gcd(a,b); if(c%r) { printf("Impossible\n"); continue; } a/=r; b/=r; c/=r; exgcd(a,b,k1,k2); t=c*k1/b;//注 1 k1=c*k1-t*b; if(k1<0) k1+=b; printf("%I64d\n",k1); } return 0; } 6、 Least Common Multiple acm.hdu.edu/showproblem.php?pid=1019 这道题目是要求出多个数的最小公倍数, n 个数的最小公倍数我们最容易想到的思路 求 就是求出两个数的最小公倍数, 然后再用这个最小公倍数与第三个数球最小公倍数, 依次下 去就可以求出 n 个数的最小公倍数了。 至于两个数的最小公倍数我们从上面的习题中已经可 以知道方法了。 a*b=gcd(a,b)*lcm(a,b); 那么我们考虑这种方法的复杂度,会发现我们要求出 n 个数的 gcd,那么我们又更好的选择 吗?是的,想想我们小学时间最开始学习最小公倍数小、最大公约数的时候,那时间我们是 怎么求的呢?我们采用了一种叫做短除法的算法。 示例如下:
2|__12______16_______24__ 2| 6 8 12 2| 3 4 6 此时我们发现 3 、4、 6 是互质的,所以 12、16、24 的最小公倍数就是 2*2*2*3*4*6=576 当然这种方法的代码难度会略高于上一种思路。 附上代码(第一种思路) : #include intgcd(intx,int y) { returnx?gcd(y%x,x):y; } int main() { inti,j,n,m,ret,tem; scanf("%d",&;n); while(n--) { scanf("%d",&;m); scanf("%d",&;ret); m--; while(m--) { scanf("%d",&;tem); ret=ret/gcd(ret,tem)*tem; } printf("%d\n",ret); } } 7、 C Looooops poj.org/problem?id=2115 扩展欧几里德,不是太裸的题目: 意思是输入 4 个数:a, b, c, k;(0<=a, b, c<2^k, 1= d(c, 2^k),先判断是否有解; 若有解,方程两边除以 gcd:因为 gcd(c/gcd, 2^k/gcd)= 1,所以用扩展欧几里德算法可 求出: x0*(c/gcd) + y0*(2^k/gcd) = 1;因此两边乘以 temp/gcd 得 x*(c/gcd) + y*(2^k/gcd) = temp/gcd. 此 x 就是满足题目(x*c ≡ temp(mod 2^k))的解。 代码: #include longlongextended_gcd(long long a, long long b, long long&;x, long long&;y) { longlong ret, tmp; if (!b) { x = 1, y = 0; return a; } ret = extended_gcd(b, a % b, x, y); tmp = x; x = y; y = tmp - a / b * y; return ret; } longlongmodular_linear_equation(long long a, long long b, long long n) {
longlong x, y, e; longlong d = extended_gcd(a, n, x, y); if (b % d) return -1; e = b / d * x % n + n; return e % (n / d); } int main() { longlong a, b, c, ans; int k; while (scanf("%lld %lld %lld %d", &;a, &;b, &;c, &;k) == 4) { if (a == 0 &;&; b == 0 &;&; c == 0 &;&; k == 0) break; ans = modular_linear_equation(c, b - a, 1LL << k); if (ans == -1) puts("FOREVER"); else printf("%lld\n", ans); } return 0; } 8、 兔子的烦恼(一) acm.nyist.net/JudgeOnline/problem.php?pid=189 这个题目其实也是很简单的。模拟就能过,但是用些数论的知识会很快的解决掉的。 分析:当 n,m 的最大公约数大于 1,设最大公约数是 k,不妨设 m=a*k,n=b*k,那么第一轮进 入的洞是 0, m,2m,...(x-1)*m(不妨假设 x*m>n,(x-1)*m1, 所以狼没办法遍历所有的洞,于是兔子躲过一劫! 当 n,m 的最大公约数等于 1,即互质,刚开始的证明同上,而 k=1,说明狼可以遍历所 有的洞,说得更白话点:只要洞口号是 1 的倍数,狼就可以进去。于是兔子就成了狼的美味 了! 代码: #include intgcd(inty,int x) { returnx?gcd(x,y%x):y; } int main() { intm,n; while(scanf("%d%d",&;m,&;n)!=EOF) { if(gcd(m,n)==1) printf("NO\n"); else printf("YES\n"); } } 9、 兔子的烦恼(二) acm.nyist.net/JudgeOnline/problem.php?pid=317 这道题目同上面的题目差不多, 只是比上面的略微复杂一点, 思路是一样的所以直接上代码 了: #include intgcd(inty,int x) { returnx?gcd(x,y%x):y;
} int main() { intm,n,k,i; while(scanf("%d%d",&;m,&;n)!=EOF) { if(gcd(m,n)==1) printf("NO\n"); else { k=gcd(m,n); printf("%d ",n-(n-1)/k-1); i=0; while(i 于这样的问题,最简单的思路就是拿 1 到√ 之间的数去一一试除了。当然可行,但是这 里介绍一种更为快捷的办法。 基于数论的一个基本定理:我们知道任何一个大于 1 的整数 n 我们都可以写作这样的形式 n=∏ 其中 为 n 的素因子。 那么这个 n 的因子个数就是∏ 1 ,利用这个结论这个题目就可以很快算出来了。 代码如下(采用第一种思路) : #include #include int main() { inti,j,k,l,m,n; scanf("%d",&;m); while(m--) { scanf("%d",&;n); n=n+1; l=sqrt(double(n)); for(i=2,k=0;i<=l;i++) { if(n%i==0) k++; } printf("%d\n",k); } } 采用第二种思路: #include #include #include int prime[100006]; int visit[100006]; intpos=0; intgetprime(int n) { memset(visit,0,sizeof(visit));
for(long long i=2;i