BZOJ 3930:[CQOI 2015]選択数の配達

3930:[CQOI 2015]選択数
Time Limit:20 Sec
メモリLimit:256 MB
タイトル接続
http://www.lydsy.com/JudgeOnline/problem.php?id=3930
Description
 区間[L,H](L,Hは整数)の中からN個の整数を選択して、全部で(H-L＋1)^N種の方案があることを知っています.このようにして選出された数の最大公約数の法則について、彼は各案のN個の整数に対して最大公約数を求め、さらに研究することにした.しかし、彼は仕事の量が多すぎるとすぐに気づき、あなたに助けを求めました.あなたの任務は簡単です.小さなzさんは整数Kを教えてくれます.彼の最大公約数はちょうどKのための選択案がいくつありますか?方案数が大きいので、1000万007で割った余りを出力してください.
Input
行を入力して、4つのスペースで区切られた正の整数を含み、順にN,K,L,Hとなります.
Output
求められたスキームの数の整数を出力します.
Sample Input
2 2 2 2 4
Sample Output
3
HINT
題意
 
クイズ:
f[i]がgcdでK*iの選択スキーム数にぴったりであれば、各i記Lはa/(K*i)の上でRを整数にしてb/(K*i)とすると、彼の方案数は(R-L+1)^N-(R-L+1)の上でf[i](a=1,2,3...)を減じて、最後のf[1]であることに注意して、a=K=1の全体を選択する必要があります.
回転:http://blog.csdn.net/shiyukun1998/article/details/44922391
はっきり言いました
コード:
 

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)  
#define maxn 100001
#define mod 1000000007
#define eps 1e-9
int Num;
char CH[20];
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
//**************************************************************************************
int pow_mod(int x, int k) 
{  
    int ans=1;  
    while(k) {  
        if(k & 1) ans = 1LL * ans * x % mod;  
        x = 1LL * x * x % mod;  
        k >>= 1;  
    }  
    return ans;  
}  
int ans[maxn];
int main()
{
    //test;
    int n,k,a,b;
    n=read(),k=read(),a=read(),b=read();
    int l=a/k,r=b/k;
    if(a%k)l++;
    for(int i=maxn-1;i>=1;i--)
    {
        int L=l/i,R=r/i;
        if(l%i)L++;
        if(l<=r)
        {
            ans[i]=pow_mod(R-L+1,n);
            ans[i]=(ans[i]-(R-L+1)+mod)%mod;
            for(int j=i*2;j<maxn;j+=i)
                ans[i]=(ans[i]-ans[j]+mod)%mod;
        }
    }
    if(l==1)
        ans[1]=(ans[1]+1)%mod;
    P(ans[1]);
}