codeforces 457D CGCDSSQ
全是公式懒得搬了= =
题解
$f[i][x]$表示以$i$为左端点的区间中,$gcd=x$的有多少个。
由右到左进行转移,赋初值$f[i][a_i]=1$:
$f[i][gcd(x,a_i)]=\sum f[i+1][x]$
因为对于以$a_i$为左端点的区间$gcd$,最多只有$log_a_i$种取值(每次$gcd$至少减小一半),所以第二维其实只有$log_a_i$个有值。我们可以用map代替第二维,并滚动第一维。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <cstdio> #include <map> using namespace std; map <int, long long> ans, f[2]; map<int,long long>::iterator it; int n, m, a[100010], T, p; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); f[0][a[n]] = 1, ans[a[n]]++; for (int i = n - 1, cur = 0; i >= 1; --i) { cur ^= 1, f[cur].clear(), f[cur][a[i]] = 1; for (it = f[cur ^ 1].begin(); it != f[cur ^ 1].end(); ++it) f[cur][gcd(it->first, a[i])] += it->second; for (it = f[cur].begin(); it != f[cur].end(); ++it) ans[it->first] += f[cur][it->first]; } scanf("%d", &T); while (T--) scanf("%d", &p), printf("%lld\n", ans[p]); } |