2010-1157

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

动态归划，状态依然是dp[i][j]表示前i个数，总和为j。转移的关键是求得[x, y]区间内的数b[i]和a[i]的最大公约数g可能的取值和对应的b[i]的个数。显然gcd一定是a[i]的约数，所以可以通过枚举a[i]的约数来枚举g，然后要求[x, y]区间内有多少b[i]满足gcd(a[i], b[i]) = g。这个只要转为求得[0, y]区间内有多少不同的数b满足gcd(a[i], b) = 1就可以了。如果y = a[i] – 1，那么这就是欧拉函数，而对于一般情况，这个问题可以通过容斥原理得到求解。 
http://watashi.ws/blog/1515/zojmonthly1010/ZOJ3412/

动态归划，状态依然是dp[i][j]表示前i个数，总和为j。转移的关键是求得[x, y]区间内的数b[i]和a[i]的最大公约数g可能的取值和对应的b[i]的个数。显然gcd一定是a[i]的约数，所以可以通过枚举a[i]的约数来枚举g，然后要求[x, y]区间内有多少b[i]满足gcd(a[i], b[i]) = g。这个只要转为求得[0, y]区间内有多少不同的数b满足gcd(a[i], b) = 1就可以了。如果y = a[i] – 1，那么这就是欧拉函数，而对于一般情况，这个问题可以通过容斥原理得到求解。

http://watashi.ws/blog/1515/zojmonthly1010/ZOJ3412/