「题解」黑暗塔 wizard
本文将同步发布于：
题目
题意简述
给定 \(y\)，求 \(\varphi(x)=y\) 中 \(x\) 的个数和最大值。
\(1\leq y\leq 10^{12}\)。
题解
欧拉函数
解决这个问题，就必然要知道欧拉函数的计算式是什么。
显然，欧拉函数的计算式子为：
\[\varphi(x)=\prod_{p_i}(p_i-1)p_i^{c_i-1}
\]
\]
我们不难想到，若 \((p_i-1)\mid y\)，那么 \(x\) 可能含有 \(p_i\) 这个质因数，我们直接搜索即可。
复杂度证明
冷静分析，我们不难发现，最劣情况下，一个数 \(y\) 满足 \(x\) 含有 \(p_i\)，则 \((p_i-1)p_i\mid y\)，因此本质不同的质因子个数最多有 \(11\) 个，我们参考反素数的贪心分析，不难写出搜索程序找到最劣情况，发现搜索状态数不多（数量级在 \(10^6\)）。
时间复杂度得到了保证。
拓展阅读
个数：A014197。
最大值：A057635。
参考程序
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
bool st;
inline ll max(reg ll a,reg ll b){
return a>b?a:b;
}
const int S=1e6;
bool vis[S+1];
int tot,prime[S+1];
inline void Init(reg int n){
for(reg int i=2;i<=n;++i){
if(!vis[i])
prime[++tot]=i;
for(reg int j=1;j<=tot&&i*prime[j]<=n;++j){
vis[i*prime[j]]=true;
if(!(i%prime[j]))
break;
}
}
return;
}
inline bool isPrime(reg ll x){
if(x<=S)
return !vis[x];
else{
for(reg int i=1;i<=tot&&1ll*prime[i]*prime[i]<=x;++i)
if(!(x%prime[i]))
return false;
return true;
}
}
int cnt;
ll Max;
vector<ll> V;
inline void dfs(reg ll y,reg int p,reg ll pod){
if(y==1){
++cnt;
Max=max(Max,pod);
return;
}
if(y+1>V[p]&&isPrime(y+1))
++cnt,Max=max(Max,pod*(y+1));
for(reg int i=p+1,siz=V.size();i<siz&&1ll*(V[i]-1)*(V[i]-1)<=y;++i)
if(!(y%(V[i]-1))){
reg ll ny=y/(V[i]-1),npod=pod*V[i];
dfs(ny,i,npod);
while(!(ny%V[i]))
ny/=V[i],npod*=V[i],dfs(ny,i,npod);
}
return;
}
bool ed;
int main(void){
Init(S);
int t;
scanf("%d",&t);
while(t--){
ll y;
scanf("%lld",&y);
V.clear();
V.push_back(2);
for(reg int i=2;i<=tot;++i)
if(!(y%(prime[i]-1)))
V.push_back(prime[i]);
cnt=Max=0;
dfs(y,0,1),dfs(y,0,2);
reg ll bas=2;
while(!(y&1))
y>>=1,bas<<=1,dfs(y,0,bas);
printf("%d %lld\n",cnt,Max);
}
fprintf(stderr,"%.3lf s\n",1.0*clock()/CLOCKS_PER_SEC);
fprintf(stderr,"%.3lf MiB\n",(&ed-&st)/1048576.0);
return 0;
}
版权声明：本文为Lu-Anlai原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。