url: https://www.luogu.com.cn/problem/P2568tag:数论，欧拉函数，筛法，前缀和思路：假设又两个互质的整数a, b，则gcd(a, b) = 1，那么对于任意的自然数p有gcd(a p, b p) = p。利用这个结论，对于这道题我们可以先求欧拉函数，然后求一遍gcd(a, b) = 1 的前缀和，这里求前…