Codeforces 83 D. Numbers

問題

自然数a,b,kが与えられる。
区間[a,b]に、最小の約数がkであるような整数はいくつあるか答えよ。

制約条件

a,b,k≦2*10^9

方針

n以下の最小の約数がkであるような整数の数を求められればよい。
これは、n/k以下の数のうち、k未満の数で割り切れない整数の数に等しい。

これは包除原理を使って求めることができる。
全てのk未満の素数について愚直にやるとTLEするが、自明な枝刈りをしてやると通る。

ソースコード

vi primes;
bool p[50000];
set<int> ok;
int ans;
void rec(int m,int k,int pos,ll prod,int sign){
	if(prod>m)return;
	if(!ok.count(prod)){
		ok.insert(prod);
		ans+=m/prod*sign;
	}
	if(primes[pos]>min(m,k-1))return;
	rec(m,k,pos+1,prod*primes[pos],-sign);
	if(prod*primes[pos]<=m)rec(m,k,pos+1,prod,sign);
}
int solve(int n,int k){
	for(int i=2;i*i<=k;i++)if(k%i==0)return 0;
	ans=0;
	ok.clear();
	rec(n/k,k,0,1,1);
	return ans;
}
void run()
{
	primes.clear();
	for(int i=2;i<50000;i++)if(!p[i]){
		primes.pb(i);
		for(ll j=(ll)i*i;j<50000;j+=i)p[j]=1;
	}
	
	int l,r,k;
	cin>>l>>r>>k;
	cout<<solve(r,k)-solve(l-1,k)<<endl;
}