fork(1) download
copy 
  1. #include <time.h>
  2. #define ll long long
  3. #define rep(i,l,r)for(ll i=l;i<r;i++)
  4. #define main signed main(){clock_t start=clock();
  5. #define ret printf("\n%.3f sec\n",(double)(clock()-start)/CLOCKS_PER_SEC);return 0;}
  6.  
  7. #define M 10000000
  8. ll memo[M+10];// memo[n] is length of the recurring cycle of 1/n
  9. ll d[M+10];// d[n] is a smallest prime divisor of n if n is composite, is 0 if n is prime
  10. ll ans;
  11.  
  12. void maked(ll n){d[0]=-1;d[1]=1;for(int i=2;i*i<=n;i++)if(!d[i])for(int j=i*i;j<=n;j+=i)if(!d[j])d[j]=i;}
  13. int div(ll n,ll*a){int cnt=0;while(d[n]){a[cnt++]=d[n];n/=d[n];};a[cnt++]=n;return cnt;}
  14. ll pom(ll a,ll n,int m){return n?pom(a%m*(a%m)%m,n/2,m)*(n&1?a%m:1)%m:1;}
  15. ll gcd(ll p,ll q){return q?gcd(q,p%q):p;}
  16. ll lcm(ll p,ll q){return p/gcd(p,q)*q;}
  17.  
  18.  
  19.  
  20. ll f(ll n){
  21. 	n/=n&-n;
  22. 	while(n%5==0)n/=5;
  23. 	if(n==1)return 0;
  24. 	if(memo[n])return memo[n];
  25. 	if(!d[n]){
  26. 		//n is prime
  27. 		ll a[100],cnt,i=0,s=n-1;
  28. 		cnt=div(n-1,a);
  29. 		while(i<cnt){
  30. 			ll m=a[i];
  31. 			while(a[i]==m){
  32. 				if(pom(10,s/m,n)==1)s/=m;
  33. 				i++;
  34. 			}
  35. 		}
  36. 		return memo[n]=s;
  37. 	}else{
  38. 		//n is composite
  39. 		ll s=1,c=0,m=d[n];
  40. 		while((n/s)%m==0)s*=m,c++;
  41. 		if(n==s){
  42. 			//n is power of prime
  43. 			if(pom(10,memo[n/m],n)==1)return memo[n]=memo[n/m];
  44. 			else return memo[n]=memo[n/m]*m;
  45. 		}else{
  46. 			//otherwise
  47. 			return memo[n]=lcm(memo[s],memo[n/s]);
  48. 		}
  49. 	}
  50. }
  51.  
  52. main
  53. maked(M);
  54. rep(i,2,M+1)ans+=f(i);
  55. printf("%lld",ans);
  56. ret
  57.  
Success #stdin #stdout 3s 165696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4937464337289
3.000 sec
https://ideone.com/o2jJyg
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!