Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // get prime factors of a using pre-generated sieve
- std::vector<int> getPrimeFactors(int a, const std::vector<int> & primes) {
- std::vector<int> f;
- for (auto p : primes) {
- if (p > a) break;
- if (a % p == 0) {
- f.push_back(p);
- do {
- a /= p;
- } while (a % p == 0);
- }
- }
- if (a > 1) f.push_back(a);
- return f;
- }
- // find coprime pairs A_i and B_j
- // A_i and B_i <= 1e9
- void solution(const std::vector<int> & A, const std::vector<int> & B) {
- // generate prime sieve
- std::vector<int> primes;
- primes.push_back(2);
- for (int i = 3; i*i <= 1e9; ++i) {
- bool isPrime = true;
- for (auto p : primes) {
- if (i % p == 0) {
- isPrime = false;
- break;
- }
- }
- if (isPrime) {
- primes.push_back(i);
- }
- }
- int N = A.size();
- struct Entry {
- int n = 0;
- int64_t p = 0;
- };
- // cntp[X] - number of times the product X can be expressed
- // with prime factors of A_i
- std::map<int64_t, int64_t> cntp;
- for (int i = 0; i < N; i++) {
- auto f = getPrimeFactors(A[i], primes);
- // count possible products using non-repeating prime factors of A_i
- std::vector<Entry> x;
- x.push_back({ 0, 1 });
- for (auto p : f) {
- int k = x.size();
- for (int i = 0; i < k; ++i) {
- int nn = x[i].n + 1;
- int64_t pp = x[i].p*p;
- ++cntp[pp];
- x.push_back({ nn, pp });
- }
- }
- }
- // use Inclusion–exclusion principle to count non-coprime pairs
- // and subtract them from the total number of prairs N*N
- int64_t cnt = N; cnt *= N;
- for (int i = 0; i < N; i++) {
- auto f = getPrimeFactors(B[i], primes);
- std::vector<Entry> x;
- x.push_back({ 0, 1 });
- for (auto p : f) {
- int k = x.size();
- for (int i = 0; i < k; ++i) {
- int nn = x[i].n + 1;
- int64_t pp = x[i].p*p;
- x.push_back({ nn, pp });
- if (nn % 2 == 1) {
- cnt -= cntp[pp];
- } else {
- cnt += cntp[pp];
- }
- }
- }
- }
- printf("cnt = %d\n", (int) cnt);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement