P1050 循环 (欧拉定理解法)

翻遍了这里洛谷的所有题解都没找到用欧拉定理做的

欧拉定理:

\[a^{\varphi(n)} \equiv 1 (\bmod n),\gcd(a,n)=1 \]

欧拉定理有一种推广:

\[A^B\bmod C=A^{B\%\varphi(C)+\varphi(C)} \bmod C , B\ge \varphi(C) \]

也就是说,本题中循环长度可以为 \(\varphi(10^k)\)

很可惜,这个循环长度并不是题目所要求的最小

但是,显然最小的循环长度一定是任意一种合法的循环长度的因子

比如 \(2^i (\bmod 7)\) 为

2 4 1 2 4 1 2 4 1 ...

我用欧拉定理求出来循环节为 \(\varphi(7)=6\),而最小循环节为 \(3\) ,\(3\) 是 \(6\) 的因子

那么我们通过打表可以发现

\[\varphi(10^k)=4\times 10^{k-1}=2^{k+1}\times 5^{k-1} \]

那么我们就可以通过枚举质因子 2 和 5 的个数来枚举所有 \(\varphi(10^k)\) 的因子,然后对每一个因子 \(n^{2^i\times 5^j}\) 进行快速幂检测是否合法,若合法就更新一下答案

这时候计算一下复杂度,枚举因子 \(k^2\),快速幂最多做 \(\log_2(10^{100})=332\) 次乘法,设 \(N\) 为 \(n\) 的位数,每次乘法最多是 \(N^2\) 的复杂度

总时间复杂度为 \(O(k^2\times N^2 \times 332)\),好像不太行的亚子呢

我们发现瓶颈出在快速幂上面,我们要搞出一种快速求 \(n^{2^i\times 5^j}\) 的算法

设 \(dp_{i,j}=n^{2^i\times 5^j}\)

边界条件:\(dp_{0,0}=n\)

那么我们先把 \(j=0\) 的一遍递推求出

\(dp_{i,0}=dp_{i-1,0}^2\)

因为显然,\(n^{2^i}=n^{2^{i-1}+2^{i-1}}=n^{2^{i-1}}\times n^{2^{i-1}}\)

然后,\(dp_{i,j}=dp_{i,j-1}^5\)

因为,\(n^{2^i\times 5^j}=n^{5\times (2^i\times 5^{j-1})}=(n^{2^i\times 5^{j-1}})^5\)

我们就可以得到一个非常优秀的 \(O(k^2\times N^2 \times 5)\)

看上去还是得 TLE

高精压8位把 \(N\) 变成 \(\frac n 8\)

这样总时间复杂度为 \(O(k^2\times N^2\times 5+k^2\times N^2\times 3)\)

忽略常数那就是 \(O(k^2\times N^2)\)

常数实在太大以至于要开Ofast才能过但还是450ms真菜

// This code wrote by chtholly_micromaker(MicroMaker)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
const int MaxN=150;
const int base=100000000;
const int pow10[]={1,10,100,1000,10000,100000,1000000,10000000,100000000};
int s[MaxN],k;
struct Bigint
{
	int a[MaxN],n;
	inline void clear()
	{
		memset(a,0,sizeof a);
		n=1;
		return;
	}
	inline void work()
	{
		while(n>1&&!a[n])
			--n;
		return;
	}
	inline Bigint read()
	{
		memset(s,0,sizeof s);
		clear();
		reg int cnt=0;
		reg char c=getchar();
		while(!isdigit(c))
			c=getchar();
		while(isdigit(c))
			s[++cnt]=c^'0',c=getchar();
		for(int i=1;i<=(cnt>>1);++i)
			swap(s[i],s[cnt-i+1]);
		n=0;
		for(int i=1;i<=cnt;i+=8)
		{
			++n;
			a[n]+=s[i+7]*10000000;
			a[n]+=s[i+6]*1000000;
			a[n]+=s[i+5]*100000;
			a[n]+=s[i+4]*10000;
			a[n]+=s[i+3]*1000;
			a[n]+=s[i+2]*100;
			a[n]+=s[i+1]*10;
			a[n]+=s[i+0]*1;
		}
		work();
		return *this;
	}
	inline void write() const
	{
		printf("%lld",a[n]);
		for(int i=n-1;i;--i)
			printf("%08lld",a[i]);
		puts("");
		return;
	}
	inline Bigint operator * (const Bigint &nt) const
	{
		Bigint res;res.clear();
		res.n=min(105ll,n+nt.n);
		for(int i=1;i<=n;++i)
			for(int j=1;j<=nt.n;++j)
				if(i+j-1<=k)
					res.a[i+j-1]+=a[i]*nt.a[j];
		for(int i=1;i<=res.n;++i)
			res.a[i+1]+=res.a[i]/base,res.a[i]%=base;
		res.work();
		return res;
	}
	inline bool operator < (const Bigint &nt) const
	{
		if(n!=nt.n)
			return n<nt.n;
		for(int i=n;i;--i)
			if(a[i]!=nt.a[i])
				return a[i]<nt.a[i];
		return false;
	}
};
template <class t> inline void read(t &s)
{
	s=0;
	reg int f=1;
	reg char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')
			f=-1;
		c=getchar();
	}
	while(isdigit(c))
		s=(s<<3)+(s<<1)+(c^48),c=getchar();
	s*=f;
	return;
}
inline bool issame(const Bigint &a,const Bigint &b)
{
	int T=k/8;
	for(int i=1;i<=T;++i)
		if(a.a[i]!=b.a[i])
			return false;
	reg int lim=pow10[k-T*8];
	return a.a[T+1]%lim==b.a[T+1]%lim;
}
inline Bigint fastpow(Bigint a,int b)
{
	reg Bigint res;res.clear();
	res.a[1]=1;
	for(;b;b>>=1,a=a*a)
		if(b&1)
			res=res*a;
	return res;
}
Bigint A,B,t,two,five;
Bigint ans;
Bigint fivepow[150],twopow[150];
Bigint dp[150][150];
signed main(void)
{
	A.read();
	read(k);
	if(A.a[1]==1&&A.n==1)
	{
		puts("0");
		return 0;
	}
	if(A.a[1]==0&&A.n==1)
	{
		puts("0");
		return 0;
	}
	if(issame(A*A,A))
	{
		puts("1");
		return 0;
	}
	two.clear();
	five.clear();
	ans.clear();
	ans.a[1]=-1;
	two.a[1]=2;
	five.a[1]=5;
	{
		for(int i=0;i<k;++i)
			fivepow[i].clear();
		fivepow[0].a[1]=1;
		for(int i=1;i<k;++i)
			fivepow[i]=fivepow[i-1]*five;
	}
	{
		for(int i=0;i<=k+1;++i)
			twopow[i].clear();
		twopow[0].a[1]=1;
		for(int i=1;i<=k+1;++i)
			twopow[i]=twopow[i-1]*two;
	}
	{
		for(int i=0;i<=k+1;++i)
			for(int j=0;j<k;++j)
				dp[i][j].clear();
		dp[0][0]=A;
		for(int i=1;i<=k+1;++i)
			dp[i][0]=dp[i-1][0]*dp[i-1][0];
		for(int i=0;i<=k+1;++i)
			for(int j=1;j<k;++j)
				dp[i][j]=dp[i][j-1]*dp[i][j-1]*dp[i][j-1]*dp[i][j-1]*dp[i][j-1];
//				dp[i][j]=fastpow(dp[i][j-1],5);
	}
	for(int i=0;i<=k+1;++i)
	{
		for(int j=0;j<k;++j)
		{
			if(!i&&!j)
				continue;
			B=twopow[i]*fivepow[j];
			t=dp[i][j]*A;
			if(issame(t,A))
			{
				if(ans.a[1]==-1||B<ans)
					ans=B;
			}
		}
	}
	ans.write();
	return 0;
}
// phi(10^k) = 4*10^(k-1)
上一篇:数论学习笔记


下一篇:CF809E Surprise me!