本文主要是介绍【bzoj3930】【SCOI2015】【选数】【容斥】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
我们知道，从区间[L,H]（L和H为整数）中选取N个整数，总共有(H-L+1)^N种方案。小z很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的N个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小z会告诉你一个整数K，你需要回答他最大公约数刚好为K的选取方案有多少个。由于方案数较大，你只需要输出其除以1000000007的余数即可。
Input
输入一行，包含4个空格分开的正整数，依次为N，K，L和H。
Output
输出一个整数，为所求方案数。
Sample Input
2 2 2 4
Sample Output
3
HINT
样例解释
所有可能的选择方案：(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)
其中最大公约数等于2的只有3组：(2, 2), (2, 4), (4, 2)
对于100%的数据，1≤N,K≤10^9，1≤L≤H≤10^9，H-L≤10^5
题解：本来想的是莫比乌斯反演,然后发现很麻烦而且复杂度不是很科学就放弃了。
考虑原题让你求l-r中gcd(i,j)=k的个数。
等价于求l/k-r/k中gcd(i,j)=1的个数.
我们设d[i]表示l/k-r/k中gcd(i,j)=i的个数,
容斥一下即可.注意特判所有数都相等的情况。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#define P 1000000007
#define LL long long
#define N 100010
using namespace std;
LL ans,d[N],l,r,ll,rr,L,R;
int sum,t,k,n,f;
LL power(LL a,int b){LL ans;for(ans=1;b;b>>=1,(a*=a)%=P) if (b&1) (ans*=a)%=P;return ans;
}
int main(){scanf("%d%d%d%d",&n,&k,&L,&R);if (k>=L&&k<=R) f=1;l=(L-1)/k;r=R/k;t=r-l;for (int i=t;i>=1;i--){ll=l/i;rr=r/i;LL sum(0);int tt=rr-ll;if (rr>ll){sum=(power((LL)(rr-ll),n)-tt+P)%P;for (int j=i<<1;j<=t;j+=i) sum=(sum-d[j]+P)%P;}d[i]=sum;}cout<<d[1]+f<<endl;
}这篇关于【bzoj3930】【SCOI2015】【选数】【容斥】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
