HDU 1852 Beijing 2008数学論
1554 ワード
タイトルの住所: http://acm.hdu.edu.cn/showproblem.php?pid=1852
この問題はHU 1452と似ています.
n,kを一つあげます.2008^nの全因子の和(1と自分を含む)%kを求めて、mを得て、2008^m%kを出力します.
私のHU 1452の問題を見て、ここで注意しなければならないことがあります.
s=(2^(3 n+1)-1)(251^(n+1)/250
gcd(250,k)は必ずしも1に等しくないので、逆元を求める方法で解決することはできません.
kは小さいですから、kを250に掛けて、最後の結果を250に割り出すことができます.
(t/250)%k=(t%(250**)/250
ACコード:
この問題はHU 1452と似ています.
n,kを一つあげます.2008^nの全因子の和(1と自分を含む)%kを求めて、mを得て、2008^m%kを出力します.
私のHU 1452の問題を見て、ここで注意しなければならないことがあります.
s=(2^(3 n+1)-1)(251^(n+1)/250
gcd(250,k)は必ずしも1に等しくないので、逆元を求める方法で解決することはできません.
kは小さいですから、kを250に掛けて、最後の結果を250に割り出すことができます.
(t/250)%k=(t%(250**)/250
ACコード:
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=52;
const LL II=29;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
LL love(LL a,LL b,LL c)
{
LL ans=1;
while(b)
{
if(b&1) ans=(ans*a)%c;
a=(a*a)%c;
b=b>>1;
}
return ans%c;
}
int main()
{
int i,j,T;
LL n,k,t;
while(scanf("%I64d%I64d",&n,&k)&&(n+k))
{
k=k*250;
t=(love(2,3*n+1,k)-1)*(love(251,n+1,k)-1);
t=(t%k+k)%k/250;
k/=250;
printf("%I64d
",love(2008,t,k));
}
return 0;
}
/*
1 10000
0 0
*/