最近做网站开发有前途没,5188站长平台,中职网页设计与制作教材,哪个协会要做网站建设啊题目的意思很简单#xff0c;求给定区间内的gcdk的个数#xff0c;这应该是传统的莫比乌斯反演了。 有两种思路#xff0c;一种是直接将里面变成gcd1#xff0c;然后里面看作元函数用莫比乌斯函数和恒等函数展开#xff0c;然后改变求和顺序。 还有一种是构造两个函数求给定区间内的gcdk的个数这应该是传统的莫比乌斯反演了。 有两种思路一种是直接将里面变成gcd1然后里面看作元函数用莫比乌斯函数和恒等函数展开然后改变求和顺序。 还有一种是构造两个函数一个是f(x)表示x|gcd的数对个数一个是g(x)表示xgcd的数对个数。则f(x)等于g(d)求和其中x|d然后再用莫比乌斯反演得到g(x)的表达式为了缩小求值范围我们可以也将gcd变成1然后求g(1)。
通过这两种方法都不难得到最后的表达式即mu(x)*f(x)求和问题就在于如何求mu(x)上因为这里x特别的大我们显然是不能线性求得的这里就要用到杜教筛。然后筛得的结果用map储存。
详见代码因为时间不太多然后写数学公式太复杂所以以后有时间再进行更新
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includectime
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e75;
const int mod1000000007;
int prime[MAXN],mobius[MAXN],sum[MAXN];
bool check[MAXN]; int tot;
mapint,int Sum;ll quick_pow(ll a,ll b,ll p)
{ll ret1; a%p;while(b){if(b1) retret*a%p; aa*a%p; b1;}return ret;
}void pre()
{tot0; mobius[1]1; sum[1]1; ll x;for(int i2;iMAXN;i){if(!check[i]){prime[tot]i; mobius[i]-1;}for(int j0;jtot (ll)prime[j]*i(ll)MAXN;j){xprime[j]*i; check[x]true;if(i%prime[j]) mobius[x]-mobius[i];else{ mobius[x]0;break;}}sum[i]sum[i-1]mobius[i];}}ll getSum(int x)
{if(xMAXN) return sum[x];if(Sum[x]) return Sum[x]; //如果已经计算过的直接返回ll ret1;for(int l2,r;lx;lr1){rx/(x/l); ret-(r-l1)*getSum(x/l);//杜教筛也用分块处理}return Sum[x]ret;
}int N,K,L,H;int main()
{pre();while(~scanf(%d%d%d%d,N,K,L,H)){L(L-1)/K; HH/K; //这里要求的gcd为L-H范围内的通过这样可以得到H/k向下取整和L/K向上取整-1的效果。实际计算的式子是H/k-L/K1ll ans0;for(int l1,r;lH;lr1){rH/(H/l);//除法分块if(lL) rmin(r,L/(L/l));//当有两个取整函数的时候要注意需要一个一个判断一下因为有可能把除数变成0这种错误很隐蔽需要特别注意ans(getSum(r)-getSum(l-1))*quick_pow(H/l-L/l,N,mod); ans%mod;}printf(%lld\n,(ansmod)%mod);}return 0;
}
