C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 496K, 提交时间: 2019-04-19 23:02:08

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll fact[105], cnt;
void getFact(ll x) {
	ll p = 2;
	while (p*p <= x) {
		if (x%p == 0) {
			while (x%p == 0)x /= p;
			fact[cnt++] = p;
		}
		p++;
	}
	if (x > 1)fact[cnt++] = x;
}

ll dfs(ll pos, ll x, ll n) {
	if (pos == cnt) return n / x;
	return dfs(pos + 1, x, n) - dfs(pos + 1, x*fact[pos], n);
}

int main() {
	ll L, R, k; cin >> L >> R >> k;
	if (R - L < 2 * k) cout << 0 << endl;
	else {
		getFact(k * 2);
		cout << dfs(0, 1, R - 2 * k) - dfs(0, 1, L == 0 ? 0 : L - 1) << endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 488K, 提交时间: 2019-04-19 20:50:09

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int _=1e5+5;
ll L,R,k,a[_],cnt,ans;
void init(ll x){
	for(ll i=2;i*i<=x;++i)
		if(x%i==0){
			a[++cnt]=i;
			while(x%i==0)x/=i;
		}
	if(x>1)a[++cnt]=x;
}
int main(){
	cin>>L>>R>>k; if(L==0)++L;
	R-=k*2; k*=2; init(k);
	if(L>R)cout<<0<<endl,exit(0);
	for(int i=0;i<(1<<cnt);++i){
		ll x=1;
		for(int j=1;j<=cnt;++j)
			if(i>>(j-1)&1)x*=-a[j];
		ans+=R/x-(L-1)/x;
	}
	cout<<ans<<endl;
}