博客

题集


hdu 4335

总的思想：暴力

ep=euler§

1.第一部分当n!<ep时，直接算n^(n!)的取值。

2第二部分当n<ep&&n!<ep时，利用欧拉降幂，求解。

3第三部分n>=ep时,那么根据欧拉降幂，指数固定为ep,式子变成n^ep,只有n变化。

而由于mod p,所以固定n变化的

循环节长度为p

.

坑点在于数据范围，用unsigned long long ，而且当b=0,p=1,M=2^64-1时，答案为M+1，会爆unsiigned long long。

#include <cstdio>
#include <cstring>
using namespace std;
typedef unsigned long long ll;
ll b,P,ep,ans,M;
ll euler(ll x)
{
    ll res=x;
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            res-=(res/i);
            while(x%i==0)
                x/=i;
        }
    }
    if(x>1)
        res-=(res/x);
    return res;
}
ll e_pow(ll x,ll y)
{
    ll res=1;
    x%=P;
    while(y)
    {
        if(y&1)
            res=res*x%P;
        x=(x%P)*(x%P)%P;
        y>>=1;
    }
    return res%P;
}
void solve()
{
    ll tmp=1;
    ans=0;
    for(ll i=1;i<ep&&i<=M;i++)
    {
        tmp=tmp*i%ep+ep;
        if(e_pow(i,tmp)==b)
            ans++;
    }
    for(ll i=ep;i<=M&&i<ep+P;i++)//一个循环节内寻找，
    {
        if(e_pow(i,ep)==b)
            ans=ans+(M-i)/P+1;
    }
    if(b==0)
        ans++;
    printf("%I64u\n",ans);
}
int main()
{
    int t,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64u%I64u%I64u",&b,&P,&M);
        printf("Case #%d: ",++cas);
        ep=euler(P);
        if(P==1&&b==0)
        {
            if(M==18446744073709551615)
                printf("18446744073709551616\n");
            else
                printf("%I64u\n",M+1);
            continue;
        }
        solve();
    }
    return 0;
}

zoj2674

#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
ll M,p;
map<int,int>mp;
void init(int x)
{
    M=1;
    for(int i=1;i<=x;i++)
        M*=i;
}
ll euler(ll x)
{
    ll res=x;
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            res-=(res/i);
            while(x%i==0)
                x/=i;
        }
    }
    if(x>1)
        res-=(res/x);
    return res;
}
ll POW(ll x,ll y,ll mod)
{
    ll res=1;
    while(y)
    {
        if(y&1)
            res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res%mod;
}
ll solve(ll x,ll mod)
{
    if(mod==1)//求极限
        return 0;
    ll phi=euler(mod);
    return POW(x,solve(x,phi)%phi+phi,mod)%mod;//递归
}
int main()
{
    int m;
    bool f=1;
    while(scanf("%lld%d",&p,&m)!=EOF)
    {
        init(m);
        if(!f)
            puts("");
        else
            f=0;
        printf("%lld\n",solve(p,M));
    }
    return 0;
}

hdu2837

和上面那题思路一样

#include <cstdio>//欧拉降幂
#include <cstring>
using namespace std;
typedef long long ll;
ll euler(ll x)
{
    ll res=x;
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            res-=(res/i);
            while(x%i==0)
                x/=i;
        }
    }
    if(x>1)
        res-=(res/x);
    return res;
}
ll f_pow(ll a,ll b,ll mod)
{
    ll res=1;
    while(b)
    {
        if(b&1)
        {
            res=res*a;
            if(res>=mod)
                res=res%mod+mod;
        }
        a=a*a;
        if(a>=mod)
            a=a%mod+mod;
        b>>=1;
    }
    return res;
}
ll dfs(ll a,ll b)
{
    if(a==0)
        return 1;
    ll tmp=euler(b);
    return f_pow(a%10,dfs(a/10,tmp),b);
}
int main()
{
    int t;
    ll n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",dfs(n,m)%m);
    }
    return 0;
}

uva10692

同样是递归的思路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int m,n;
int a[14];
ll euler(ll x)
{
    ll res=x;
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            res-=(res/i);
            while(x%i==0)
                x/=i;
        }
    }
    if(x>1)
        res-=(res/x);
    return res;
}
ll POW(ll x,ll y,ll mod)
{
    ll res=1;
    while(y)
    {
        if(y&1)
            res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res%mod;
}
ll solve(int num,ll mod)
{
    if(num==n)
        return a[num]%mod;//注意取模，WA
    ll phi=euler(mod);
    return POW((ll)a[num],solve(num+1,phi)%phi+phi,mod)%mod;
}
int main()
{
    int cas=0;
    char cc;
    while(scanf("%c",&cc),cc!='#')
    {
        m=0;
        m=cc-'0';
        while(1)
        {
            cc=getchar();
            if(cc==' ')
                break;
            m*=10;
            m+=cc-'0';
        }
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        getchar();
        printf("Case #%d: %lld\n",++cas,solve(1,m));
    }
    return 0;
}
/*
10 4 2 3 4 5
100 2 5 2
53 3 2 3 2
*/