bzoj 3884 19南京区域赛网络赛 B. super_log（扩展欧拉定理）
发布时间
阅读量：
阅读量
BZOJ 3844
19南京B. super_log
扩展欧拉定理
BZOJ 3844 传送门 （幂塔函数）
**题意：
给你p求值。**
思路：扩展欧拉。
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <math.h>
#define mems(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int N=1e7+10;
ll tao(ll n)//求[1,n)中与n互质的数的个数
{
ll ans=n;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
ans-=ans/i;
while(n%i==0)
n/=i;
}
}
if(n>1)
ans-=ans/n;
return ans;
}
ll MOD(ll a,ll mod)
{
if(a<mod)
return a;
return a%mod+mod;
}
ll power(ll a,ll b,ll c)
{
ll ans=1;
while(b)
{
if(b&1)
{
ans=MOD(ans*a,c);
}
b>>=1;
a=MOD(a*a,c);
}
return ans;
}
ll solve(ll p)
{
if(p==1)
return MOD(1,p);
return power(2,solve(tao(p)),p);
}
int main()
{
printf("%lld\n",tao());
int t;
scanf("%d",&t);
while(t--)
{
ll p;
scanf("%lld",&p);
printf("%lld\n",solve(p)%p);
}
return 0;
}19南京区域赛网络赛 B. super_log
题意：求a(a(a(a(...))),一共有b个a，求对于mod取余后的结果。
**思路：扩展欧拉
**
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <math.h>
#define mems(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int N=1e7+10;
bool vis[N]; //质数为0 素数为1
ll prime[N]; //1-N 所有质数
ll phi[N]; //欧拉筛
void init(ll N) //[1-N)范围内 素数欧拉筛
{
mems(vis,false);
vis[0]=vis[1]=true;
phi[1] = 1;
ll cnt = 0;
for(ll i = 2; i < N; i ++)
{
if(!vis[i]){
prime[cnt++] = i;
phi[i] = i - 1;
}
for(ll j = 0; j < cnt && i * prime[j] < N; j ++)
{
vis[i * prime[j]] = true;
if(i % prime[j] == 0){
phi[i*prime[j]] = phi[i]*prime[j];
break;
}
else{
phi[i*prime[j]] = phi[i]*phi[prime[j]]; // phi[i]*(prime[j]-1);
}
}
}
}
ll tao(ll n)//求[1,n)与n互质的数的数目
{
ll ans=n;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
ans-=ans/i;
while(n%i==0)
n/=i;
}
}
if(n>1)
ans-=ans/n;
return ans;
}
ll MOD(ll a,ll mod)//这里就实现了判断x是否大于φ(p);
{//扩展欧拉定理的二三情况
if(a<mod)
return a;
return a%mod+mod;
}
ll power(ll a,ll b,ll c)
{
ll ans=1;
while(b)
{
if(b&1)
{
ans=MOD(ans*a,c);
}
b>>=1;
a=MOD(a*a,c);
}
return ans;
}
ll solve(ll a,ll b,ll mod)
{
if(b==0)
return MOD(1,mod);
if(mod==1)
return MOD(a,mod);
return power(a,solve(a,b-1,phi[mod]),mod);
}
int main()
{
init(1e6+5);
int t;
scanf("%d",&t);
while(t--)
{
ll a,b,m;
scanf("%lld%lld%lld",&a,&b,&m);
printf("%lld\n",solve(a,b,m)%m);
}
return 0;
}全部评论 (0)
还没有任何评论哟~