fork download
copy 
  1. // SRM 683, d1-med, by Errichto
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. const int mod = 1e9 + 7;
  5. const int nax = 1e7 + 5;
  6. bool isPrime[nax];
  7. vector<int> primes;
  8. set<pair<int,int>> s[nax/10];
  9. map<int,int> occurrences; // occurrences of primes
  10.  
  11. int mapuj[nax]; // primes into compressed numbers
  12. int true_value[nax/10]; // true value of compressed prime number
  13.  
  14. struct Factor {
  15. 	map<int,int> m;
  16. 	Factor(){}
  17. 	Factor(int n) {
  18. 		for(int p : primes) {
  19. 			int x = true_value[p];
  20. 			if(x * x > n) break;
  21. 			while(n % x == 0) {
  22. 				n /= x;
  23. 				++m[p];
  24. 			}
  25. 		}
  26. 		if(n > 1) {
  27. 			assert(isPrime[n]);
  28. 			++m[mapuj[n]];
  29. 		}
  30. 		// for(pair<int,int> p : m) printf("%d:%d ", p.first, p.second);
  31. 		// puts("");
  32. 	}
  33. 	void eat(Factor & other) {
  34. 		// I am LCM, 'other' is GCD
  35. 		map<int,int> m2;
  36. 		for(pair<int,int> p : other.m) {
  37. 			auto it = m.find(p.first);
  38. 			if(it != m.end()) {
  39. 				int tmp = (*it).second;
  40. 				m2[p.first] = min(tmp, p.second);
  41. 				m[p.first] = max(tmp, p.second);
  42. 			}
  43. 			else m[p.first] = p.second;
  44. 		}
  45. 		other.m = m2;
  46. 	}
  47. 	void add_to_structures(int i) {
  48. 		for(pair<int,int> p : m) {
  49. 			occurrences[p.first]++;
  50. 			s[p.first].insert(make_pair(p.second, i));
  51. 		}
  52. 	}
  53. 	void remove_from_structures(int i) {
  54. 		for(pair<int,int> p : m) {
  55. 			if(occurrences[p.first] == 1) occurrences.erase(p.first);
  56. 			else --occurrences[p.first];
  57. 			s[p.first].erase(make_pair(p.second, i));
  58. 		}
  59. 	}
  60. } t[nax/10];
  61.  
  62. class GCDLCM2 {
  63. 	public : int getMaximalSum(vector <int> start, vector <int> d, vector <int> cnt) {
  64.  
  65. 		for(int i = 2; i < nax; ++i) isPrime[i] = true;
  66. 		for(int i = 2; i * i < nax; ++i) if(isPrime[i])
  67. 			for(int j = i * i; j < nax; j += i) isPrime[j] = false;
  68. 		int T = 0;
  69. 		for(int i = 2; i < nax; ++i) if(isPrime[i]) {
  70. 			++T;
  71. 			primes.push_back(T);
  72. 			true_value[T] = i;
  73. 			mapuj[i] = T;
  74. 		}
  75.  
  76. 		vector<int> in;
  77. 		for(int i = 0; i < (int) start.size(); ++i)
  78. 			for(int j = 0; j < cnt[i]; ++j)
  79. 				in.push_back(start[i] + d[i] * j);
  80.  
  81. 		int n = (int) in.size();
  82. 		if(n < 50) {
  83. 			for(int x : in) printf("%d ", x);
  84. 			puts("");
  85. 		}
  86.  
  87. 		for(int i = 0; i < n; ++i) {
  88. 			t[i] = Factor(in[i]);
  89. 			t[i].add_to_structures(i);
  90. 		}
  91.  
  92. 		int answer = n;
  93. 		while(!occurrences.empty()) {
  94. 			set<int> bigs;
  95. 			for(pair<int,int> p : occurrences) {
  96. 				int prime = p.first;
  97. 				auto it = s[prime].end();
  98. 				--it;
  99. 				bigs.insert((*it).second); // I'm adding index i \in [0,n-1]
  100. 			}
  101. 			int lcm = *(bigs.begin()); // index i
  102. 			t[lcm].remove_from_structures(lcm);
  103. 			for(int other : bigs) if(other != lcm) {
  104. 				t[other].remove_from_structures(other);
  105. 				t[lcm].eat(t[other]);
  106. 				t[other].add_to_structures(other);
  107. 			}
  108. 			int mul = 1;
  109. 			for(pair<int,int> p : t[lcm].m)
  110. 				for(int i = 0; i < p.second; ++i)
  111. 					mul = (long long) mul * true_value[p.first] % mod;
  112. 			answer = (answer + mul) % mod;
  113. 			t[lcm].m.clear();
  114. 			answer = (answer + mod - 1) % mod;
  115. 			//for(int b : bigs) printf("%d ", b);
  116. 			//return -124;
  117. 		}
  118. 		return answer;
  119.  
  120. 	} 
  121. };
  122.  
  123. int main() {
  124. 	class GCDLCM2 o;
  125. 	vector<int> in = vector<int>{4,6,12,18,1000003};
  126. 	vector<int> tmp; while(tmp.size() < in.size()) tmp.push_back(1);
  127. 	typedef vector<int> vi;
  128. 	vi a = vi{5,6};
  129. 	vi b = vi{23,45};
  130. 	vi c = vi{50000,50000};
  131. 	printf("%d\n", o.getMaximalSum(a,b,c));
  132. 	//printf("%d\n", o.getMaximalSum(in, tmp, tmp));
  133. 	return 0;
  134. }
  135.  
  136.  
Success #stdin #stdout 1.43s 123776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
804225394
https://ideone.com/BCOUcE
language:
C++14 (gcc 8.3)
created:
8 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!