【bzoj3930】【SCOI2015】【选数】【容斥】-白红宇的个人博客

【bzoj3930】【SCOI2015】【选数】【容斥】

发布日期：2021-11-16 15:38:13 浏览次数：9 分类：技术文章

本文共 1218 字，大约阅读时间需要 4 分钟。

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

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
     
      #include
      
       #include
       
        #define P 1000000007#define LL long long#define N 100010using 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<
        
         <

转载地址：https://blog.csdn.net/sunshinezff/article/details/50956283 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【bzoj3529】【SDOI2014】【数表】【莫比乌斯反演+树状数组】

下一篇：【bzoj2154】【Crash的数字表格】【莫比乌斯反演】

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！