all pair gcd product

sabbirh654's blog

By sabbirh654, history, 5 years ago, In English

how can I solve this problem? Any hints ? here is the problem link :

-5

sabbirh654
5 years ago
11

Comments (7)

Show archived | Write comment?

xanaxxx

5 years ago, hide # |

how can I solve this problem? with patience

→ Reply

rguy23

5 years ago, hide # |

how can I solve this problem? look at the editorial

→ Reply

balalaika

5 years ago, hide # |

-10

Let's have $$$f(n, x) = gcd(1, x) * gcd(2, x) * ... gcd(n, x)$$$. Then answer is $$$f(n, 1) * f(n, 2) * ... * f(n, m)$$$

Since $$$g(x) = gcd(a, x)$$$ is multiplicative function over $$$x$$$ then $$$f(x) = f(n, x)$$$ is multiplicative function over $$$x$$$ too. So you can calculate all $$$f(x)$$$ for $$$x$$$ in $$$[1..m]$$$ for $$$O(m)$$$.

→ Reply

EnterYourName

5 years ago, hide # ^ |

kinda like my approach right?

→ Reply

balalaika

5 years ago, hide # ^ |

Not really sure how your approach works and implements. But maybe in nutshell they same. I don't mean any inclusion/exclusion, just dp.

→ Reply

EnterYourName

5 years ago, hide # |

← Rev. 3 →

UPD: AC code

Code

#include <iostream>

const int M = (int) 1e9 + 7, N = (int) 15e6;
int primes[N + 1], gcd[N + 1], k;

int binExp(int a, int n) {
    int ans = 1;
    while(n) {
        if(n & 1) ans = 1ll * a * ans % M;
        a = 1ll * a * a % M;
        n >>= 1;
    }
    return ans;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    int n, m, num, p;
    long long ans = 1;
    std::cin >> n >> m;

    gcd[1] = 1;

    for(int i = 2; i <= n; i++) {
        if(!primes[i]) {
            primes[k++] = i;
            gcd[i] = binExp(i, m / i);
        }

        for(int j = 0; j < k && 1ll * primes[j] * i <= n; j++) {
            primes[i * primes[j]] = 1;

            if(i % primes[j] == 0) {
                num = i, p = 1;
                while(num % primes[j] == 0) num /= primes[j], p *= primes[j];

                gcd[i * primes[j]] = 1ll * gcd[num] * gcd[p] % M * binExp(primes[j], m / (p * primes[j])) % M;
                break;
            }  
            else gcd[i * primes[j]] = 1ll * gcd[i] * gcd[primes[j]] % M;
        }

        ans = ans * gcd[i] % M;
    }
    
    std::cout << ans << '\n';
}

→ Reply