bzoj3930: [CQOI2015] 선택(Dp)

제목 전송문.
해법:이 문제와 사고방식이 꽤 비슷하다.공인수로서 반드시 최대 공인수가 되는 것은 아니다.그렇다면 공인수로 구하는 방안은 간단하다.몇 개의 수가 그의 배수인지 알기만 하면 된다.그리고 숫자^N을 쓰면 돼요.f[i]는 최대 공통 인수가 i*K인 스키마를 나타냅니다.그럼 공인수부터 계산해.그리고 f[i의 배수]를 빼면 되잖아.
코드 구현:

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
ll n,k,l,r;ll f[110000];const ll mod=1000000007;
ll pow_mod(ll a,int b) {
    ll ans=1;a%=mod;
    while(b!=0) {if(b%2==1)ans=(ans*a)%mod;a=(a*a)%mod;b/=2;}
    return ans;
}
int main() {
    scanf("%lld%lld%lld%lld",&n,&k,&l,&r);
    ll L=l/k,R=r/k;if(l%k)L++;
    for(int i=R-L+1;i>=1;i--) {
        ll LL=L/i,RR=R/i;if(L%i)LL++;
        if(LL<=RR) {
            f[i]=pow_mod(RR-LL+1,n);f[i]=(f[i]-(RR-LL+1)+mod)%mod;
            for(int j=i*2;j<=R-L+1;j+=i) f[i]=(f[i]-f[j]+mod)%mod;
        }
    }if(L==1)f[1]++,f[1]%=mod;
    printf("%lld
",f[1]);
    return 0;
}