題干：

Beijing 2008

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/65535 K (Java/Others)
Total Submission(s): 917????Accepted Submission(s): 394

?

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.?
?

?

?

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

?

?

Author

lxlcrystal@TJU

?

題意：求2008^n的所有因子和m對k取余，然后求2008^m對k取余。

解題報告：

這題是類似的一題，可以除法可以通過求逆元。因為那題的mod是29，gcd(2*166,29)==1，存在逆元。但是這里的gcd(250,k)不一定滿足等于1，也就是說不一定存在逆元。那么觀察我們要求的m，m肯定有250這個分母，所以可以表示成m=x/250。m%k=(x/250)%k轉(zhuǎn)化為(x%(250*k))/250。求變成了先除法再取余了。

?

AC代碼：

#include<bits/stdc++.h> #define LL long long using namespace std;LL q_pow(LL a,LL k,LL mod){LL ans=1;while(k){if(k&1){ans=(ans*a)%mod;}k>>=1;a=(a*a)%mod;}return ans; } // 那么觀察我們要求的m，m肯定有250這個分母， // 所以可以表示成m=x/250。m%k=(x/250)%k轉(zhuǎn)化為(x%(250*k))/250。求變成了先除法再取余了。 int main() {int n,k;LL a,b,ans;while(~scanf("%d%d",&n,&k) ) {if(n==0&&k==0) break;a=q_pow(2,3*n+1,250*k)-1;b=q_pow(251,n+1,250*k)-1;//mod取250*k，目的是先要保留250這個因子，放在取余后再除ans=(a*b)%(250*k);ans/=250;ans=((ans%k)+k)%k;printf("%lld\n",q_pow(2008,ans,k));}return 0 ; }

類似的一題：

https://blog.csdn.net/qq_41289920/article/details/81190874

總結(jié)

以上是生活随笔為你收集整理的【HDU - 1852】 Beijing 2008（）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。