fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fo(i,n) for(i=0;i<n;i++)
  4. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  5. #define ll long long
  6. #define pb push_back
  7. #define mp make_pair
  8. #define F first
  9. #define S second
  10. #define all(x) x.begin(), x.end()
  11. #define clr(x) memset(x, 0, sizeof(x))
  12. #define sortall(x) sort(all(x))
  13. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  14. #define PI 3.1415926535897932384626
  15. typedef pair<int, int>	pii;
  16. vector<ll> primes;
  17. const int NN = 1e6+1;
  18. int prime[2*NN];
  19. void seive(){
  20.     ll i;
  21.     Fo(i, 1, 2*NN) prime[i] = i;
  22.     for(i=2; i < 2*NN; i++){
  23.         if (prime[i] == i){
  24.             for(ll j = 2*i; j < 2*NN; j += i)
  25.                 if (prime[j] == j)
  26.                     prime[j] = i;
  27.             primes.pb(i);
  28.         }
  29.     }
  30. }
  31.  
  32. typedef ll var;
  33. pair<var, var> extended_gcd(var a, var b){
  34. 	bool swp = 0;
  35. 	if (a<b) swap(a, b), swp = 1;
  36. 	//1 = N*a + M*b
  37. 	//returns {N, M}
  38. 	vector<var> K;
  39. 	var k, r, FF, SS;
  40. 	while(1){
  41. 		k = a/b;
  42. 		r = a - k*b;
  43. 		if(r == 1){
  44. 			FF = 1, SS = -k;
  45. 			reverse(all(K));
  46. 			for(int k: K){
  47. 				var tem = FF;
  48. 				FF = SS;
  49. 				SS = tem - SS * k;
  50. 			}
  51. 			return swp?mp(SS, FF):mp(FF, SS);
  52. 		}
  53. 		else{
  54. 			K.pb(k);
  55. 		}
  56. 		a = b;
  57. 		b = r;
  58. 		//{1, k}
  59. 	}
  60. }
  61. var solve(var a, var b, var n){
  62. 	pair<var, var> ans = extended_gcd(a, n);
  63. 	var x = ( ans.F * b ) % n;
  64. 	if ( x < 0)
  65. 		x += n;
  66.  
  67. 	//a*x is b (mod n)
  68. 	return x;
  69.  
  70. }
  71. int main()
  72. {
  73. 	ios_base::sync_with_stdio(false);
  74. 	cin.tie(NULL);
  75. 	int i,n,k,j;
  76. 	i = 2;
  77. 	seive();
  78. 	ll sum = 0;
  79. 	ll PO[30];
  80. 	PO[0] = 1;
  81. 	Fo(j, 1, 20) PO[j] = 10*PO[j-1];
  82. 	while(primes[i] < NN){
  83. 		int p1 = primes[i];
  84. 		int p2 = primes[i+1];
  85. 		int r = p2-p1;
  86. 		int d = 0;
  87. 		int v = p1;
  88. 		while(v) v/=10, d++;
  89. 		ll a = PO[d];
  90. 		sum += solve(a, p2-p1, p2) * a + p1;
  91. 		i++;
  92. 	}
  93. 	cout<<sum<<endl;
  94. 	return 0;
  95. }
Success #stdin #stdout 0.08s 11400KB
comments (?)
stdin 
0 0
stdout 
18613426663617118
https://ideone.com/p54ZJg
my template :)
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!