BZOJ3884题解上帝与集合的正确用法--扩展欧拉定理

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=3884

分析

扩展欧拉定理裸题

欧拉定理及证明:

如果$(a,m)=1$,则$a^{\phi(m)} \equiv 1 \mod m$

$Prove:$设$x$取遍$m$的缩系,则$ax$取遍$m$的缩系,即

\[\prod x = \prod ax \mod m
\]

因为这样的$a$有$\phi(m)$个

\[\prod x = \prod x *a^{ \phi(m)} \mod m
\]

由于$(x,m)=1$,保证$\prod x$ 存在模$m$意义下的逆元

所以 $$a^{ \phi(m)} \equiv 1 \mod m$$
扩展欧拉定理:

如果 $$(a,m)!=1$$

则 $$a^b \equiv a^{min(b,b % \phi(m)+\phi(m))} \mod m$$

设$f(x)$为在模$x$意义下题目式子的值,那么$$f(x)=2^{2{^{...}}%\phi(x)+\phi(x)} \mod x=2^{f(\phi(x))+\phi(x)} \mod x$$

然后就可以记忆化搞一搞了

注意

求欧拉函数可以线性预处理也可以直接求,实践证明直接求不知道快到哪里去了

代码:

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cctype>

#define ll long long

#define ri register int

using std::sort;

template <class T>inline void read(T &x){

	x=0;int ne=0;char c;

	while(!isdigit(c=getchar()))ne=c=='-';

	x=c-48;

	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;

	x=ne?-x:x;return ;

}

const int maxn=10000005;

const int inf=0x7fffffff;

int t,n;

int mem[maxn];

int phi[maxn];

bool vis[maxn];

inline void get_table(){

	bool is_pri[maxn];

	int num[1000005],tot=0,tmp;

	memset(is_pri,0,sizeof(is_pri));

	is_pri[1]=1;

	phi[1]=1;

	for(ri i=2;i<=maxn;i++){

	    //printf("%d\n",i);

		if(!is_pri[i]){

			num[++tot]=i;

			phi[i]=i-1;

		}

		for(ri j=1;j<=tot;j++){

			tmp=num[j]*i;

			if(tmp>=maxn)break;

			is_pri[tmp]=1;

			if(i%num[j]==0){

				phi[tmp]=num[j]*phi[i];

				break;

			}

			else {

				phi[tmp]=(num[j]-1)*phi[i];

			}

		}

	}

	return ;

}

inline int get_phi(int x){

	int res=x;

	for(ri i=2;i*i<=n;i++){

		if(x%i==0){

			res=res/i*(i-1);

			while(x%i==0)x=x/i;

		}

	}

	if(x>1)res=res/x*(x-1);

	return res;

}

int ksm(ll x,int c,int p){

	ll ans=1,res=x;

	while(c){

		if(c&1)ans=ans*res%p;

		res=res*res%p;

		c=c>>1;

	}

	return ans%p;

}

int f(int x){

	if(x==1)return 0;

	if(vis[x])return mem[x];

	int p=phi[x];//int p=get_phi(x);

	vis[x]=1;

	mem[x]=ksm(2,f(p)+p,x);

	return mem[x];

}

int main(){

	read(t);

	get_table();

	while(t--){

		read(n);

		printf("%d\n",f(n));

	}

	return 0;

}

巴特西

BZOJ3884题解上帝与集合的正确用法--扩展欧拉定理

题目链接

分析

注意

代码:

最新文章

热门文章