本文共 2155 字，大约阅读时间需要 7 分钟。
给定n，k，l，r
问从[l, r]中选出n个数gcd为k的方案数。
解：稍微一想就能想到反演，F(x)就是[l, r]中x的倍数个数的n次方。
后面那个莫比乌斯函数随便怎么搞都行，当然因为这是杜教筛的题就杜教筛了。
然后写一写，交上去80分......
然后枚举一下d是k的多少倍，我们发现F(x)的计算式[(r / x) - ((l - 1) / x)]n可以整除分块...
然后就做完了。
1 #include 2 #include 3 #include 4 5 typedef long long LL; 6 const int N = 1000010, T = 1000008; 7 const LL MO = 1000000007; 8 9 std::map mp;10 int p[N], top, miu[N];11 LL n, k, l, r, Miu[N], L, R;12 bool vis[N];13 14 inline void getp(int n) {15 miu[1] = 1;16 for(int i = 2; i <= n; i++) {17 if(!vis[i]) {18 p[++top] = i;19 miu[i] = -1;20 }21 for(int j = 1; j <= top && i * p[j] <= n; j++) {22 vis[i * p[j]] = 1;23 if(i % p[j] == 0) {24 break;25 }26 miu[i * p[j]] = -miu[i];27 }28 }29 for(int i = 1; i <= n; i++) {30 Miu[i] = Miu[i - 1] + miu[i];31 }32 return;33 }34 35 inline LL qpow(LL a, LL b) {36 LL ans = 1;37 a %= MO;38 while(b) {39 if(b & 1) ans = ans * a % MO;40 a = a * a % MO;41 b = b >> 1;42 }43 return ans;44 }45 46 LL getMiu(LL x) {47 if(x <= 0) return 0;48 if(x <= T) return Miu[x];49 if(mp.count(x)) return mp[x];50 LL ans = 1;51 for(LL i = 2, j; i <= x; i = j + 1) {52 j = x / (x / i);53 ans -= (j - i + 1) % MO * getMiu(x / i) % MO;54 ans %= MO;55 }56 return mp[x] = (ans + MO) % MO;57 }58 59 LL F(LL x) {60 LL temp = (R / x) - (L / x);61 return qpow(temp, n);62 }63 64 int main() {65 getp(T);66 scanf("%lld%lld%lld%lld", &n, &k, &l, &r);67 LL ans = 0;68 L = (l - 1) / k, R = r / k;69 for(LL i = 1, j; i <= R; i = j + 1) {70 if(L / i) j = std::min(R / (R / i), L / (L / i));71 else if(R / i) j = R / (R / i);72 else j = R;73 ans += F(i) * (getMiu(j) - getMiu(i - 1)) % MO;74 ans %= MO;75 }76 printf("%lld\n", (ans + MO) % MO);77 78 return 0;79 }
整除分块的时候要判断是不是0啊......
转载于:https://www.cnblogs.com/huyufeifei/p/10444324.html
