[BZOJ3930] [CQOI2015]选数 递推

记f[i]为gcd恰好为K*i的选数方案数

那么对于每一个i 记L为 a/(K*i) 上取整 R为 b/(K*i) 那么他的方案数就为

(R-L+1) ^ N – (R-L+1) 再减去f[a*i] (a = 1,2,3….)

最后的f[1]即为答案 注意若a/K上取整 == 1 那么全部选K也是一种方案 需要+1

#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<set>#include<map>#define SF scanf#define PF printfusing namespace std;typedef long long LL;int N, K, a, b, L, R;const int MOD = 1000000007;const int MAXN = 100000;int prime[MAXN+10], mu[MAXN+10], tot;LL fac[MAXN+10], inv[MAXN+10];int d[MAXN*2+10];int ans = 0;bool vis[MAXN+10];int pow_mod(int x, int k) {int ans = 1;while(k) {if(k & 1) ans = 1LL * ans * x % MOD;x = 1LL * x * x % MOD;k >>= 1;}return ans;}int main() {SF("%d%d%d%d", &N, &K, &a, &b);int l = a / K, r = b / K;if(a % K) l++;for(int i = MAXN; i >= 1; i–) {int L = l / i, R = r / i;if(l % i) L++;if(l <= r) {d[i] = pow_mod(R-L+1, N);d[i] = (d[i] – (R-L+1) + MOD) % MOD;for(int j = i*2; j <= MAXN; j+= i) d[i] = (d[i] – d[j] + MOD) % MOD;}}if(l == 1) d[1] = (d[1] + 1) % MOD;PF("%d", d[1]);}

，就是去旅行。牵着彼此的手，