歐拉的托特函數排列

我在SPOJ上做了這個問題。 www.spoj.com/problems/TIP1。我已經寫了這段代碼，但我在判斷時超出了時間限制。任何人都可以幫助我進行任何優化或更好的方法。如果N是正整數，則PHI（N）是其中GCD（N，K）= 1且1≤K≤N的整數K的數目。我們表示GCD是最大公約數。例如，我們有PHI（9）= 6。歐拉的托特函數排列

#include<iostream> 
#include<vector> 
#include<cmath> 
#include<cstdio> 
#include<algorithm> 
using namespace std; 

#define N 10000010 
#define MAXN 10000010 
int phi[MAXN + 1], prime[MAXN/10], sz=0; 
vector<bool> mark(MAXN + 1); 

int ans[10000011]; 
vector<int> a(10); 
vector<int> b(10); 

bool isprm(long int x) 
{ 

for(int s=0; s<10; s++) 
{ 
    a[s]=b[s]=0; 
} 
long int y=phi[x]; 
int i=0,j=0; 
while(x>0) 
{ 
    int rem=x%10; 
    x=x/10; 
    a[i]=rem; 
    i++; 
} 

    while(y>0) 
{ 
    int rem=y%10; 
    y=y/10; 
    b[j]=rem; 
    j++; 
} 


sort(a.begin(), a.end()); 
sort(b.begin(), b.end()); 


if(i!=j) 
return false; 

for(int s=0; s<10; s++) 
{ 
    if(a[s]!=b[s]) 
    return false; 
} 

return true; 
} 

void precompute_again() 
{ 
for(int i=0; i<=20; ++i) 
ans[i]=0; 

ans[21]=21; 

for(long int i=22; i<10000005; ++i){ 
bool chk=false; 

chk=isprm(i); 

if(chk==true) 
{ 

    if(i*phi[ans[i-1]]==phi[i]*ans[i-1]) 
    { 
     ans[i]=i; 
    } 
    else 
    { 

      if(i*phi[ans[i-1]]>phi[i]*ans[i-1]) 
      { 
       ans[i]=ans[i-1]; 
      } 
      else 
      { 
       ans[i]=i; 
      } 

    } 
} 
else 
{ 
     ans[i]=ans[i-1]; 

} 

} 


} 

int main() 
{ 

phi[1] = 1; 
for (int i = 2; i <= MAXN; i++){ 
if(!mark[i]){ 
    phi[i] = i-1; 
    prime[sz++]= i; 
} 
for (int j=0; j<sz && prime[j]*i <= MAXN; j++){ 
    mark[prime[j]*i]=1; 
    if(i%prime[j]==0){ 
     int ll = 0;int xx = i; 
     while(xx%prime[j]==0) 
     { 
         xx/=prime[j]; 
         ll++;   
        } 
     int mm = 1; 
     for(int k=0;k<ll;k++)mm*=prime[j]; 
     phi[i*prime[j]] = phi[xx]*mm*(prime[j]-1); 
     break; 
} 
    else phi[i*prime[j]] = phi[i]*(prime[j]-1); 
} 
} 


precompute_again(); 

int t; 
scanf("%d",&t); 
while(t--) 
{ 
long int m; 
scanf("%ld",&m); 
cout<<ans[m]<<endl; 
} 
return 0;  
}

來源

2015-07-10 Maroof

嘗試使用Sieve of Eratosthenes的變體。

以下代碼計算所有phi[N]高達MAXN。對於MAXN = 1e7它眨眼之間。

int i, j; 
int * phi = new int [MAXN]; 
for (i = 1; i < MAXN; i ++) 
    phi[i] = i; 

for (i = 2; i < MAXN; i ++) 
{ 
    if (phi[i] != i) continue; 
    for (j = i; j < MAXN; j += i) 
     phi[j] = phi[j]/i * (i - 1); 
}

來源

2015-07-21 00:27:06 WhatsUp

歐拉的托特函數排列

回答

相關問題