HDU1452:Happy 2004(求因子和+分解质因子+逆元）上一题的简单版
浏览数：26 /
时间：2015年06月11日
题目链接：传送门
题目要求：求S(2004^x)%29。
题目解析：
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #define mod 29 using namespace std; typedef long long ll; ll mpow(ll x,ll k) { ll t=1; while(k) { if(k&1) t=((t%mod)*(x%mod))%mod; k>>=1; x=((x%mod)*(x%mod))%mod; } return t; } ll X,Y; void extend(ll A,ll B,ll &x1,ll &y1) { if(B==0) { x1=1; y1=0; return ; } extend(B,A%B,x1,y1); ll t=x1; x1=y1; y1=t-(A/B)*y1; } int main() { int n; ll a,b,c,sum,temp; while(scanf("%d",&n)!=EOF&&n!=0) { sum=1; temp=2*n+1; a=mpow(2,temp); a=(a-1)%mod; b=mpow(3,n+1); b=(b-1)%mod; b=(b*15)%mod; c=mpow(167,n+1); c=(c-1)%mod; extend(166,29,X,Y); X=(X%mod+mod)%mod; c=(c*X)%mod; sum=((a%mod)*(b%mod)*(c%mod))%mod; printf("%I64d\n",sum); } return 0; }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
