sabbirh654's blog

all pair gcd product
By sabbirh654, history, 6 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (11)
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

how can I solve this problem? with patience

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how can I solve this problem? look at the editorial

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

$$$\prod_{i = 1}^N p_j^{\lfloor{\frac M p_j}\rfloor}$$$ if $$$i$$$ is prime else you gotta do some inclusion and exclusion principle instead of subtraction you have to divide.

→ Reply
»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    kinda like my approach right?

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        ans = 1
for i in [1, n]:
    prime factorize(i)
    for each prime p_j in i;
        sum = 0
        for each power k of prime:
              sum += M / p_j^k

        ans = p_j ^ sum * ans % mod

print ans

        This is my approach. I later realised I could do this without inclusion-exclusion. But not sure if this is right.

        → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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