Loading...

洛谷P4139 上帝与集合的正确用法

check评论:0 条 remove_red_eye浏览量:374 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-11-06

这是一道欧拉函数的裸题

先来说一下怎么线性筛欧拉函数

首先欧拉函数有几个性质

如果$i$是质数,则$ϕ(i)=i-1$

如果$j\bmod i==0$,则$ϕ(j)=ϕ(i)\times j$,否则$ϕ(j)=ϕ(i)\times (j-1)$

然后我们可以利用这个性质来线性筛欧拉函数

然后这道题,我们需要运用欧拉扩展定理,即$a^b\equiv a^{b\bmod ϕ(p)+ϕ(p)}\pmod p$,条件是$ϕ(p)\leq b$

然后这道题上面那个$2^{2^{2^{...}}}$一个递归就搞定了

#include <bits/stdc++.h>
using namespace std;
#define maxn 10000010
int phi[maxn],vis[maxn],prime[maxn],cnt;
void euler()
{
    phi[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt,i*prime[j]<maxn;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
} 
int ksm(int b,int mod)
{
    long long res=1,qaq=2;
    while(b)
    {
        if(b&1)
        {
            res=res*qaq;
            res%=mod;
        }
        qaq*=qaq;
        qaq%=mod;
        b>>=1;
    }
    return res;
}
long long solve(int mod)
{
    if(mod==1)
    {
        return 0;
    }
    return ksm(solve(phi[mod])+phi[mod],mod);
}
int main()
{
    euler();
    int t,p;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        scanf("%d",&p);
        printf("%d\n",solve(p));
    }
}

chevron_left 洛谷P2568 GCD
洛谷P4995 跳跳! chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名