题目:http://acm.hdu.edu.cn/showproblem.php?pid=1452
题意：让你求2004^x次方的因子的个数。
思路：首先，先要想到求解正整数正因数和的公式！！！分解为素数。然后套那个该死的公式，先把分子算出来。
接下来，看到mod29要敏感，29为素数，那么他就会满足费马小定理a^(p-1) mod p = 1( (a*b)%x==(a%x*b%x)%x,你a%x都==1了，你计算他还有什么意义);所以你算高次方求模，你就可以让指数mod p-1 前提是你取模的数满足是素数的条件。
最后，你mod完29你要除以(p1-1)*(p2-1).........，但是你肯定除不尽，因为分母很大，这时候就可以根据同余的概念，计算分母的逆元，直接分子*分母的逆元就好了。
逆元：a*b=1(mod m)，只要关于取模问题，分母过大，就直接可以用求逆元的做法。
总结：好题啊，可以用到好几个数论的知识，感觉数论博大精深，自己却连点皮毛都没有学好=W=
代码：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define ll __int64 ll quickmul(ll x,ll y,ll Z)//大数相乘取模，非常神奇的一个快速乘法的计算方法 { ll tmp=x/(long double)Z*y+1e-3; return (x*y+Z-tmp*Z)%Z; } ll quickmod(ll a,ll b,ll c) { ll ans=1; while(b){ if(b&1) ans=(ans*a)%c; a=quickmul(a,a,c); b>>=1; } return ans; } int main() { ll x; while(~scanf("%I64d",&x)){ if(!x) break; ll s1=quickmod(2,(2*x+1)(,29)-1;//用到了费马小定理 ll s2=quickmod(3,(x+1)(,29)-1; ll s3=quickmod(167,(x+1)(,29)-1; ll ans=(((s1*s2*s3)))*9));//9为所求解的逆元 printf("%I64d\n",ans); } }
