Problem 500!!!

The number of divisors of 120 is 16.
In fact 120 is the smallest number having 16 divisors.

Find the smallest number with 2500500?divisors.
Give your answer modulo 500500507.

前500500個(gè)質(zhì)數(shù)是第一個(gè)假的解，然后維護(hù)一個(gè)"亂七八糟的數(shù)據(jù)結(jié)構(gòu)"里面存著第一個(gè)質(zhì)數(shù)的平方，第二個(gè)質(zhì)數(shù)的平方，...，然后每次把這個(gè)數(shù)據(jù)結(jié)構(gòu)里最小的那個(gè)和當(dāng)前解最大的單冪次質(zhì)數(shù)做個(gè)比較，如果那個(gè)元素更小就替換，然后在數(shù)據(jù)結(jié)構(gòu)里推進(jìn)剛剛用來替換的那個(gè)形如p^k的數(shù)的平方......大概就這么個(gè)思路吧...

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 500500507; const ll mi = 500500+1; const ll maxn = 2e7;//從2開始，到第500500個(gè)素?cái)?shù)是7e6左右 ll a[4] = {2, 4, 8, 16}; ll prime[mi+100]; ll check[maxn], tot; void init(){memset(check, 0, sizeof(check));prime[tot++] = 1;for (ll i = 2; i < maxn; ++i){if(!check[i]){prime[tot++] = i;}if(tot == mi){break;}for (ll j = 1; j < tot; ++j){if (i * prime[j] > maxn){break;}check[i*prime[j]] = 1;if (i % prime[j] == 0){break;}}} } //快速冪，返回a^b ll Pow(ll a,ll b) {ll ret=1;while(b){if(b&1) ret=(ret*a)%mod;a=(a*a)%mod;b>>=1;}return ret; }int main(){init();priority_queue<ll>que;que.push(1);ll Size = 1;ll Top = 4;for(ll i = 1; i < mi; i++){if(Size >= mi){if(prime[i] >= que.top()){break;}else{que.pop();que.push(prime[i]);for(ll j = 0; j < Top; j++){if(Pow(prime[i], a[j]) >= prime[tot-1]){Top = j;break;}if(Pow(prime[i], a[j]) >= que.top()){Top = j;break;}else{que.pop();que.push(Pow(prime[i], a[j]));}}}}else{que.push(prime[i]);Size++;for(ll j = 0; j < Top; j++){if(Pow(prime[i], a[j]) >= prime[tot-1]){Top = j;break;}if(Size >= mi){if(Pow(prime[i], a[j]) >= que.top()){Top = j;break;}else{que.pop();que.push(Pow(prime[i], a[j]));}}else{if(Pow(prime[i], a[j]) >= prime[tot-1]){Top = j;break;}que.push(Pow(prime[i], a[j]));Size++;}}}}ll ans = 1;while(!que.empty()){ans *= que.top();que.pop();ans%=mod;}cout<<ans<<endl;return 0; } #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 500500507; const ll N = 500500; const ll L =N*16; ll np[L+1];struct xpowy{ll x,y;bool operator <(xpowy &b){return log(x)*(y+1)>log(b.x)*(b.y+1);} }; //快速冪，返回a^b ll Pow(ll a,ll b) {ll ret=1;while(b){if(b&1) ret=(ret*a)%mod;a=(a*a)%mod;b>>=1;}return ret; }int main(){vector<xpowy> v;for(ll n=2;n<=L;n++)if(!np[n]){for(ll x=n*n;x<=L;x+=n)np[x]=1;v.push_back({n,0});}make_heap(v.begin(),v.end());for(int i=0;i<N;i++){v[0].y=v[0].y*2+1;pop_heap(v.begin(),v.end());push_heap(v.begin(),v.end());}ll s=1;for(int i=0;i<v.size();i++)s=s*Pow(v[i].x,v[i].y)%mod;cout<<s; }

?

總結(jié)

以上是生活随笔為你收集整理的ProjectEuler500 【组合数学】【数论】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。