1.POJ 1150 The Last Non-zero Digit #质因数分解+模运算分治#
先贴两份题解：
http://www.hankcs.com/program/algorithm/poj-1150-the-last-non-zero-digit.html
http://www.cppblog.com/abilitytao/archive/2009/10/31/99907.html
下面是自己看完题解（划掉）之后的理解：
题目要求出组合数Anm=n!/(n-m)!（说实话一开始不知道题目中的NPM到底什么意思。。）的最后一个非零位，那么可以来看看n!的最后一个非零位该如何求得。
求n!：
（1）首先，n!的所有10因子都是要去掉的（因为求非零位），那么2和5也要一对一对的去掉；
（2）接下来把数列分成奇数列：1 2 3 4 5 6 7 8 9 10 –> 1 3 5 7 9 | 2 4 6 8 10
故有f(n )=f(n/2 )+g(n );
g(n )可以再分为：1 3 5 7 9 11 13 17 19 21 ……和5的奇数倍 5 15 25……
故设这个数列中末尾为x（x=1，3，7，9）的个数 g(n,x )=n/10+(n%10>=x)+g(n/5,x );
（3）最后再对数列中末尾为2和5的个数进行比较、特判一下即可。
代码如下：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; //计算n！中质因子（2/5）的出现次数 int get_2_5(int n,int num) { if(n==0) return 0; return n/num+get_2_5(n/num,num); } //计算奇数数列中末尾为x的数的出现次数 int g(int n,int x) { if(n==0) return 0; return n/10+(n%10>=x)+g(n/5,x); //数列还能再次分出子问题，故有g(n/5,x) } //计算数列中末尾为x的数的出现次数 int getx(int n,int x) { if(n==0) return 0; return getx(n/2,x)+g(n,x); } int table[4][4]={ 6,2,4,8,//2^n%10的循环节 1,3,9,7,//3 1,7,9,3,//7 1,9,1,9 //9 }; int main() { int n,m; while(~scanf("%d %d",&n,&m)) { int num2=get_2_5(n,2)-get_2_5(n-m,2); int num5=get_2_5(n,5)-get_2_5(n-m,5); int num3=getx(n,3)-getx(n-m,3); int num7=getx(n,7)-getx(n-m,7); int num9=getx(n,9)-getx(n-m,9); int res=1; if(num2<num5) { printf("5 "); continue; } else { if(num2!=num5) {//if num2==num5 那么res应该*1 res*=table[0][(num2-num5)%4]; res%=10; } res*=table[1][num3%4]; res%=10; res*=table[2][num7%4]; res%=10; res*=table[3][num9%4]; res%=10; } printf("%d ",res); } }
2.POJ 1284 Primitive Roots #欧拉函数#
有一个关于原根的概念：若p有原根，则它恰有φ(φ( p))个不同的原根。
欧拉函数定义：对于正整数p，<=p且与p互质的正整数（包括1）的个数记作φ( p)。
这道题其实就是求欧拉数。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int Euler(int n) { int res=n; for(int i=2;i*i<=n;i++) { while(n%i==0) { n/=i; res-=(res/i); while(n%i==0) n/=i; } } if(n>1) res-=(res/n); return res; } int main() { int p; while(~scanf("%d",&p)) printf("%d ",Euler(p-1)); return 0; }
3.POJ 2115 C Looooops #扩展欧几里得#
http://blog.csdn.net/lyy289065406/article/details/6648546
题意：
对于C，for(i=A ; i!=B ;i +=C)，在k位存储系统中循环几次才结束。
（若在有限次内结束，则输出循环次数n，否则输出FOREVER）
分析推导就直接看大牛的了，代码如下：
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<stack> #include<map> using namespace std; typedef long long ll; ll extend_gcd(ll a,ll b,ll &x,ll &y) { //return d=gcd(a,n); if(b==0) { x=1,y=0; return a; } else { ll t=extend_gcd(b,a%b,x,y); ll xx=x,yy=y; x=yy; y=xx-(a/b)*yy; return t; } } int main() { ll A,B,C,k,x,y; while(~scanf("%I64d %I64d %I64d %I64d",&A,&B,&C,&k)) { if(A==0&&B==0&&C==0&&k==0) break; ll a=C,b=B-A,n=(ll)1<<k; //n=2^k ll d=extend_gcd(a,n,x,y); if(b%d!=0) //方程无解 printf("FOREVER "); else { x=(x*(b/d))%n; //x为方程ax=b(mod n)的最小解 x=(x%(n/d)+n/d)%(n/d); //x为方程ax=b(mod n)的最小整数解 printf("%I64d ",x); } } return 0; }