2014-03-25 - HIR180's diary

■ SRM 613 D1Med 22:33

dp[x]=GCDがx*kの倍数になるものとしてやれば
適当にやるだけ。
#line 2 "RandomGCD.cpp"
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
// I'll become a member of  IOI 2015 Japan team.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i
class RandomGCD
{
	public:
	long long modpow(long long x,long long n)
	{
		long long res=1;
		while(n>0)
		{
			if(n&1) res=res*x%mod;
			x=x*x%mod;
			n>>=1;
		}
		return res;
	}
	int countTuples(int N, int K, int low, int high) 
	{
		{
			if(K>100000)
			{
				return (low<=K && K<=high);
			}
			ll val[100005];
			int gen=100000/K;
			for(int i=K;i<=100000;i+=K)
			{
				int ub=high/i;
				int lb=(low+i-1)/i;
				val[i/K]=modpow(ub-lb+1LL,N);
				int hoge=100000/i;
				//hoge+1~
				//lb~ub
				val[i/K]-=(max(0,ub-max(hoge+1,lb)+1));
				val[i/K]=(val[i/K]+mod)%mod;
			}
			for(int i=gen;i>=1;i--)
			{
				for(int j=i*2;j<=gen;j+=i)
				{
					val[i]=(val[i]-val[j]+mod)%mod;
				}
			}
			return val[1];
		}
	}
};