Beijing 2008
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/65535 K (Java/Others)
Total Submission(s): 741 Accepted Submission(s): 291
Problem Description
As
we all know, the next Olympic Games will be held in Beijing in 2008. So
the year 2008 seems a little special somehow. You are looking forward
to it, too, aren't you? Unfortunately there still are months to go. Take
it easy. Luckily you meet me. I have a problem for you to solve. Enjoy
your time.
Now given a positive integer N, get the sum S of all positive integer divisors of 2008N. Oh no, the result may be much larger than you can think. But it is OK to determine the rest of the division of S by K. The result is kept as M.
Pay attention! M is not the answer we want. If you can get 2008M, that will be wonderful. If it is larger than K, leave it modulo K to the output. See the example for N = 1，K = 10000: The positive integer divisors of 20081 are 1、2、4、8、251、502、1004、2008，S = 3780, M = 3780, 2008M % K = 5776.
Now given a positive integer N, get the sum S of all positive integer divisors of 2008N. Oh no, the result may be much larger than you can think. But it is OK to determine the rest of the division of S by K. The result is kept as M.
Pay attention! M is not the answer we want. If you can get 2008M, that will be wonderful. If it is larger than K, leave it modulo K to the output. See the example for N = 1，K = 10000: The positive integer divisors of 20081 are 1、2、4、8、251、502、1004、2008，S = 3780, M = 3780, 2008M % K = 5776.
Input
The
input consists of several test cases. Each test case contains a line
with two integers N and K (1 ≤ N ≤ 10000000, 500 ≤ K ≤ 10000). N = K = 0
ends the input file and should not be processed.
Output
For each test case, in a separate line, please output the result.
Sample Input
1 10000
0 0
Sample Output
5776
收获挺大的！。以前对于除法模运算只知道用逆元可以算，，但是当两个数不互素的时候就不知道怎么弄了。今天得到了两个公式。。第一个公式自己做的时候想到了可能可以，然后真的AC了，然后去验证发现真的有：
1.(a/b)%mod=a%(b*mod)/b%mod;(get这个公式好激动)
2.(a/b)%mod=a*b^(mod-2)%mod，mod为素数（可以通过逆元证明）（这个公式的话感觉如果mod为素数的话，直接用逆元也一样的，，可以参考我博客hdu1452）
然后这个题并不难，把2008分解成 251*2^3 然后求因子和用第一个公式去掉分母250,然后可以得到M，在用快速幂计算就好了。
#include <stdio.h> #include <iostream> using namespace std; typedef long long LL; LL pow_mod(LL a,LL n,LL mod){ LL ans = 1; while(n){ if(n&1) ans = a*ans%mod; a=a*a%mod; n=n>>1; } return ans; } int main() { LL N,K; while(scanf("%lld%lld",&N,&K)!=EOF,N&&K) { K = 250*K; LL M = ((pow_mod(251,N+1,K)-1)*(pow_mod(2,3*N+1,K)-1))%K; M = M/250; K/=250; LL ans =pow_mod(2008,M,K); printf("%lld ",ans); } return 0; }