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;
}

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： Android iOS 移动互联 终端开发

相关文章

随机文章

您可能还喜欢

您可能还喜欢