首页 > 其他 > 详细

bzoj3884: 上帝与集合的正确用法(数论)

时间:2017-10-22 01:19:00      阅读:311      评论:0      收藏:0      [点我收藏+]

  感觉是今天洛谷月赛T3的弱化版,会写洛谷T3之后这题一眼就会写了...

  还是欧拉扩展定理技术分享

  于是就在指数上递归%phi(p)+phi(p)直到1,则后面的指数就都没用了,这时候返回,边回溯边快速幂。因为一个数最多求log次phi就变成1,所以复杂度为O(logp*sqrt(p)),这题线性筛是比直接求要慢的...

  注意p=1的时候直接返回0

技术分享
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio> 
#include<algorithm>
#define ll long long 
using namespace std;
const int maxn=1010,inf=1e9;
int T,x;
int p[maxn];
void read(int &k)
{
    int f=1;k=0;char c=getchar();
    while(c<0||c>9)c==-&&(f=-1),c=getchar();
    while(c<=9&&c>=0)k=k*10+c-0,c=getchar();
    k*=f;
}
inline int phi(int x)
{
    int ans=x;
    for(int i=2;i*i<=x;i++)
    if(!(x%i))
    {
        ans=ans/i*(i-1);
        while(!(x%i))x/=i;
    }
    if(x>1)ans=ans/x*(x-1);
    return ans;
}
inline int power(int a,int b,int mod)
{
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%mod)
    if(b&1)ans=1ll*ans*a%mod;
    return ans;
}
int solve(int mod)
{
    if(mod==1)return 1;int tmp;
    return power(2,solve(tmp=phi(mod))+tmp,mod);
}
int main()
{
    read(T);
    while(T--)read(x),printf("%d\n",solve(x));
    return 0;
}
View Code

 

bzoj3884: 上帝与集合的正确用法(数论)

原文:http://www.cnblogs.com/Sakits/p/7707338.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!