bzoj 3643:Phi的反函数 (数论+搜索)

论坛 期权论坛 编程之家     
选择匿名的用户   2021-6-2 16:23   1378   0

phi的反函数

时间限制:1s 内存限制:128MB

题目描述
他已一无所有,只记得那个函数,那无数个以欧拉命名的函数之一。
Phi,定义域是 Z+,phi(n)表示 1~n 中与 n 互质的数的个数。具体地,


特殊的,phi(1)=1.
对于这个式子他知道很多种解释方法,然而他不想解释。他只想知道这个该死的函数的反函数是什么,反函数的意思是给定 x,需要求最小的n使得phi(n)=x.
输入描述
一行一个正整数x。
输出描述
一行一个正整数表示答案, 如果无解或者答案大于等于231
输出-1.
输入样例
4
输出样例
5

数据范围

对于%10的数据,x≤5
对于%30的数据,x≤10^5
对于%60的数据,x≤10^7
对于%100的数据,x<2^31


题解:数论+搜索。

这道题其实可以用线性筛水过很多分,但是想要切掉还需要暴搜一下。

数据范围最大到2^31-1,在这个范围内的数最多可以被分解成10个质因数相乘的形式。因为最小的十个质因数相乘就已经炸int了。

ans = p1^a1 * p2^a2 * …… * pm^am 其中pi是素数且对于任意i,j有pi≠pj

n = p1^(a1-1) * p2^(a2-1) * …… * pm^(am-1) * (p1-1) * (p2-1) * …… * (pm-1)

发现ans与n 应该是同阶的,大小应该接近,那么我们可以用线性筛筛出在sqrt(n)范围内的所有质数,然后暴力的去枚举判断计算答案。可能会出现有一种情况,就是pi只出现了一次,但是pi>sqrt(n)也就是不在我们筛出的范围内,因为这样的质数只有一个,所有我们需要特判一下这种情况。pi^0=1所以在运算过程中肯定没法出现pi,所以当n除以部分 p1^(a1-1) * p2^(a2-1)* (p1-1) * (p2-1) ...的答案+1是素数,就更新答案,同时不必再将其分解。假设当前得到的为now,now=p1^(a1-1) * p2^(a2-1) * …… * pm^(am-1) * (p1-1) * (p2-1) * …… * (pm-1),我们利用now还原会的原数一定大于等于now+1。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 1000003
#define LL long long
#define p 2147483647
using namespace std;
int pd[N],prime[N],phi[N],n,m;
LL ans;
void calc()
{
 phi[1]=1;
 for (int i=2;i<=m;i++)
  {
   if (!pd[i]){
    prime[++prime[0]]=i;
    phi[i]=i-1;
   }
  for (int j=1;j<=prime[0];j++)
   {
    if (i*prime[j]>m) break;
    pd[i*prime[j]]=1;
    if (i%prime[j]==0)  phi[i*prime[j]]=phi[i]*prime[j];
    else phi[i*prime[j]]=phi[i]*(prime[j]-1);
   }
  }
}
int pdprime(int x)
{
 for (int i=2;i*i<=x;i++)
  if (x%i==0) return false;
 return true;
}
void dfs(int x,int now,LL tot)
{
 if (tot>=ans) return;
 if (now==1)  {
  ans=tot;
  return;
 }
 if (now>m&&pdprime(now+1)){
  ans=min(ans,tot*((LL)now+1));
  return;
 }
 for (int i=x;i<=prime[0];i++)
 {
  if (prime[i]-1>now) break;
  if (now%(prime[i]-1)==0){
   int x=now/(prime[i]-1); LL y=tot*(LL)prime[i]; dfs(i+1,x,y);
   while (x%prime[i]==0){
    x/=prime[i]; y*=(LL)prime[i];
    dfs(i+1,x,y);
   }
  }
 }
}
int main()
{
 freopen("phi.in","r",stdin);
 freopen("phi.out","w",stdout);
 scanf("%d",&n); m=(int)sqrt(n); 
 calc(); ans=(LL)2147483647+1;
 dfs(1,n,1);
 if (ans>2147483647)  printf("-1\n");
 else   printf("%I64d\n",ans);
}


分享到 :
0 人收藏
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:3875789
帖子:775174
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP