UVa 10692 - Huge Mods（指数循环节）

#include <stdio.h>   
#include <string.h>   
#include <math.h>   
#define LL long long   
  
LL a[20];  
  
LL euler(LL n)  
{  
    LL m=(LL)sqrt(n+0.5);  
    LL ans=n;  
    for(LL i=2;i<=m;i++)  
    if(n%i==0){  
        ans=ans/i*(i-1);  
        while(n%i==0)n/=i;  
    }  
    if(n>1)ans=ans/n*(n-1);  
    return ans;  
}  
  
LL pmod(LL a,LL n,LL m)  
{  
    LL now = 1;  
    for(LL i=0;i<n;i++) {  
        now *= a;  
        if(now>=m)  break;  
    }  
    if(now >= m)   now = m;  
    else now=0;  
  
    if(n==0)return 1;  
    LL x=pmod(a,n/2,m);  
    LL ans=(LL)x*x%m;  
    if(n%2==1) ans=ans*a%m;  
    return ans+now;  
}  
  
LL solve(LL cur,LL n,LL m)  
{  
    if(cur==n-1)  
    {  
        if(a[cur]>=m)  
        return a[cur]%m+m;  
        else  
        return a[cur];  
    }  
    LL M=euler(m);  
    LL p=solve(cur+1,n,M);  
    LL ans=pmod(a[cur],p,m);  
    return ans;  
}  
  
int main()  
{  
    char s[10];  
    LL m,n;  
    int cas=0;  
    while(scanf("%s",s)==1)  
    {  
        int l=strlen(s);  
        if(s[0]=='#'&&l==1)break;  
        m=0;  
        for(int i=0;i<l;i++)  
            m=m*10+s[i]-'0';  
        scanf("%lld",&n);  
        for(int i=0;i<n;i++)  
            scanf("%lld",&a[i]);  
        printf("Case #%d: %lld\n",++cas,solve(0,n,m)%m);  
    }  
    return 0;  
}  

#include <stdio.h>
#include <string.h>
#include <math.h>
#define LL long long

LL a[20];

LL euler(LL n)
{
    LL m=(LL)sqrt(n+0.5);
    LL ans=n;
    for(LL i=2;i<=m;i++)
    if(n%i==0){
        ans=ans/i*(i-1);
        while(n%i==0)n/=i;
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}

LL pmod(LL a,LL n,LL m)
{
    LL now = 1;
    for(LL i=0;i<n;i++) {
        now *= a;
        if(now>=m)  break;
    }
    if(now >= m)   now = m;
    else now=0;

    if(n==0)return 1;
    LL x=pmod(a,n/2,m);
    LL ans=(LL)x*x%m;
    if(n%2==1) ans=ans*a%m;
    return ans+now;
}

LL solve(LL cur,LL n,LL m)
{
    if(cur==n-1)
    {
        if(a[cur]>=m)
        return a[cur]%m+m;
        else
        return a[cur];
    }
    LL M=euler(m);
    LL p=solve(cur+1,n,M);
    LL ans=pmod(a[cur],p,m);
    return ans;
}

int main()
{
    char s[10];
    LL m,n;
    int cas=0;
    while(scanf("%s",s)==1)
    {
        int l=strlen(s);
        if(s[0]=='#'&&l==1)break;
        m=0;
        for(int i=0;i<l;i++)
            m=m*10+s[i]-'0';
        scanf("%lld",&n);
        for(int i=0;i<n;i++)
            scanf("%lld",&a[i]);
        printf("Case #%d: %lld\n",++cas,solve(0,n,m)%m);
    }
    return 0;
}

补充：软件开发 , C++ ,

上一个：POJ 2142 The Balance
下一个：hdu-4632-Palindrome subsequence-记忆化dp