sabbirh654's blog

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

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

how can I solve this problem? with patience

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

how can I solve this problem? look at the editorial

»
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.

»
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)$$$.

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

    kinda like my approach right?

    • »
      »
      »
      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.

      • »
        »
        »
        »
        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.

»
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';
}