### sabbirh654's blog

By sabbirh654, history, 6 weeks ago,

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

• -5

 » 6 weeks ago, # |   +3 how can I solve this problem? with patience
•  » » 6 weeks ago, # ^ |   0 Any idea or hints ?
 » 6 weeks ago, # |   0 how can I solve this problem? look at the editorial
 » 6 weeks ago, # | ← Rev. 2 →   0 $\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, # |   -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)$.
•  » » 6 weeks ago, # ^ |   0 kinda like my approach right?
•  » » » 6 weeks ago, # ^ |   0 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, # ^ |   0 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 →   0 UPD: AC code Code#include 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'; } 
•  » » 6 weeks ago, # ^ |   0 You need just for linear time calculate factorization of all numbers. Click
•  » » » 5 weeks ago, # ^ |   0 Noice! That's really a cool algorithm and a cool blog.