CF2094H La Vaca Saturno Saturnita（1900，二分+分解因数）

Problem - 2094H - Codeforces

遍历l,r过程中， k只在遇到自己的因数时贡献会有变化，每次变化至少减少一半，变化次数log级别,考虑枚举每次变化的位置。

读入数组的时候存下ai对应的位置，查询的时候把k的因数都筛出来，枚举因数x，二分找x在l,r区间出现的第一个位置。把这些位置放进数组后排个序，遍历这个数组对k做/=操作就可以了。

筛因数复杂度sqrt(k)，k<=1e5，最多有8个因数，枚举复杂度8*log(n)，

总复杂度N(q*(sqrt(k)+8*log(n)))，可以通过本题

#include using namespace std;#define int long longconst int N = 1e6 + 10;const int mod = 998244353;#define pii pair#define lowbit(x) (x & (-x))int n;int a[N];void solve(){ int n, q; cin >> n >> q; unordered_map<int, vector> e; for (int i = 1; i > a[i]; e[a[i]].push_back(i); } while (q--) { int k, l, r; cin >> k >> l >> r; int res = 0; int las = l; vector p; for (int i = 1; i * i <= k; i++) { if (k % i == 0) { p.push_back(i); if (k / i != i)  p.push_back(k / i); } } // 分解因数 vector ned; for (int x : p) // 找因数在l,r出现的过的位置 { auto it = lower_bound(e[x].begin(), e[x].end(), l); if (it != e[x].end() && *it <= r) ned.push_back(*it); } sort(ned.begin(), ned.end()); for (int i = 0; i < ned.size(); i++) { res += (ned[i] - las) * k; int x = a[ned[i]]; while (k % x == 0) k /= x; res += k; las = ned[i] + 1; } res += (r - las + 1) * k; cout << res <> t; while (t--) solve();}