Problem 500!!! (Project Euler 500)

题目大意：
求出最小的正整数,它的约数有$2^{500500}$个。

思路：
考虑将一个数质因数分解,如果它的约数有$2^{500500}$个, 那么每个质因子的指数一定是$2^k-1$这样的形式。

如果把质因子$p$的指数从$2^k-1$增大到$2^{k+1}-1$ 那么相当于在原数的基础上乘以$p^{2^k}$.

所以就可以贪心了, 一开始把足够多的质数放进小根堆里,然后每次取出最小的$x$, 把答案乘上$x$, 然后把$x^2$ 加入堆里。

代码：

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 #include <set>

 #include <cstring>

 #include <map>

 #include <queue>

 using namespace std;

 typedef long long ll;

 #define N 10000000

 #define M 1100

 typedef pair<int,int> pii;

 bool flag[N];

 int p[N],phi[N];

 void Get_Primes()

 {

     phi[]=;

     for (int i=;i<N;i++)

     {

         if (!flag[i]) p[++p[]]=i,phi[i]=i-;

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

         {

             flag[i*p[j]]=true;

             if (i%p[j]==)

             {

                 phi[i*p[j]]=phi[i]*p[j];

                 break;

             }

             else phi[i*p[j]]=phi[i]*(p[j]-);

         }

     }

 }

 priority_queue<ll, vector<ll>, greater<ll> > Q;

 int main()

 {

     freopen("in.in","r",stdin);

     freopen("out.out","w",stdout);

     ll ans = , mod = ;

     Get_Primes();

     for (int i = ; i <= ; ++i) Q.push(p[i]);

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

     {

         ll x = Q.top();

         ans =  x % mod;

         Q.pop(), Q.push(x * x);

     }

     cout << ans << endl;

     return ;

 }

答案：35407281

巴特西

Problem 500!!! (Project Euler 500)

最新文章

热门文章