bzoj 3643Phi的反函数

3643: Phi的反函数

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 298 Solved: 192
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Output

　　这道题我只能说是一道披着搜索外衣的数学题，核心都在数学知识上，于是数学能力令人发指的我跪了……

　　在讲这道题之前我们先明确一下几点：

　　　　1.一个数x的质因子若大于sqrt(x)则这个质因子最多只有一个。

　　　　2.我们设p_k为已知数x的第k个素因子a_k为该素因子在x的素因子中有几个则φ(x)=p1^(a1-1)*(p1-1)*p2^(a2-1)*(p2-1)……

　　　　3.由1可知我们线筛只用筛到sqrt(INF)，大于它直接暴力检测。

　　　　4.由2可知如果对于一个素数p，p-1是n的因子，则p可对答案产生贡献。

　　于是知道了以上几点我们就好说多了，我们只要枚举每一个素数p，如果p-1是当前now的因子就接下去dfs并枚举a，对于那个大于sqrt(n)的因子我们直接判断如果now+1是素数且now+1>sqrt(n)，我们就检查他是否对答案有贡献。

　　不知道有没有人和我和Q某犇一样对于是now+1还是now还是now-1有疑问。为了周全，我还是说一下。如果当前now满足以上条件那么此时now=p^(a-1)*(p-1)，由于p大于sqrt(n)，a一定为1，所以就变成了now=p-1，那么p=now+1。

　　差点忘说了，我们为什么会去选择dfs这种方式呢？因为貌似可以证明，在题目给的数据最多只有10个（不同的）素因子，一个素因子最多只出现30次，所以dfs没跑。

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #define N 50005

 using namespace std;

 long long sq,n,ss[N],zz,ans=;

 bool fss[N];

 bool pri(long long x)

 {

     for(int i=;i<=sqrt(x);i++)

         if(x%i==)return ;

     return ;

 }

 void dfs(long long sum,long long wz,long long now)

 {

     if(sum>ans)return;

     if(now==)

     {

         ans=min(ans,sum);

         return;

     }

     if(now>sq&&pri(now+))ans=min(ans,(now+)*sum);

     for(int i=wz;i<=zz&&ss[i]-<=sq&&ss[i]-<=now;i++)

     {

         if(now%(ss[i]-)==)

         {

             int x=now/(ss[i]-),y=sum*ss[i];

             dfs(y,i+,x);

             while(x%ss[i]==)

             {

                 x/=ss[i],y*=ss[i];

                 dfs(y,i+,x);

             }

         }

     }

 }

 int main()

 {

     scanf("%lld",&n);

     sq=sqrt(n);

     for(int i=;i<=sqrt(n);i++)

     {

         if(!fss[i])

         {

             zz++;

             ss[zz]=i;

         }

         for(int j=;j<=zz&&i*ss[j]<N;j++)

         {

             fss[i*ss[j]]=;

             if(i%ss[j]==)break;

         }

     }

     dfs(,,n);

     if(ans<2147483648ll)

         printf("%lld\n",ans);

     else printf("-1\n");

     return ;

 }

巴特西