频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
3930: [CQOI2015]选数|递推|数论浅析
2016-03-24 09:16:48         来源:ws_yzy的博客  
收藏   我要投稿

题目让求从区间[L,H]中可重复的选出n个数使其gcd=k的方案数
转化一下也就是从区间[?Lk?,?Hk?]中可重复的选出n个数使其gcd=1的方案数
然后f[i]表示gcd=i的方案数,考虑去掉所有的数都是重复的情况,这种情况最后在判断一下加上
f[i]=sum?∑i|jf[j]

 

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define mod 1000000007 //2 3 4679 35617
#define N 100051
using namespace std;
int sc()
{
    int i=0,f=1; char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
    return i*f;
}
long long f[N],n,k,a,b;
long long cal(ll x,ll y)
{
    long long res=1;
    for(;y;x=x*x%mod,y>>=1)
        if(y&1)res=res*x%mod;
    return res;
}
int main()
{
    scanf("%d%d%d%d",&n,&k,&a,&b);
    int l=a/k,r=b/k;
    if(a%k)l++;
    for(int i=b-a;i;i--)
    {
        int L=l/i,R=r/i;
        if(l%i)L++;
        if(l<=r)
        {
            f[i]=(cal(R-L+1,n)-(R-L+1))%mod;
            for(int j=i*2;j<=b-a;j+=i)f[i]=(f[i]-f[j])%mod;
        }
    }
    if(l==1)f[1]++;
    printf("%d",(f[1]+mod)%mod);
    return 0;
}

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 数论
上一篇:windows客户端开发浅析--为你的客户端进行国际化
下一篇:Rust 提供的 lint 检查项说明分析
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站