Bazinga

The first line contains an integer T, where T is the number of test cases. T test cases follow.

For each test case, the only line contains three integers L, R and K.

• 1 ≤ T ≤ 20.

• 1≤ L ≤ R ≤10¹⁸.

• 1 ≤ K ≤ 10⁵.

C++11(clang++ 3.9) 解法, 执行用时: 407ms, 内存消耗: 464K, 提交时间: 2020-01-10 16:52:58

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}
ll pw(ll a,ll b,ll k)
{
	ll r=1;
	for(;b;b>>=1,a=a*a%k) if(b&1) r=r*a%k;
	return r;
}
int main()
{
	int T;
	ll cns=0;
	scanf("%d",&T);
	while(T--)
	{
		ll l,r,k;
		scanf("%lld %lld %lld",&l,&r,&k);
		ll cnt=(r-l+1)/k,ans=1;
		ll left=(l%k==0)?l/k:(l/k)-1,right=r/k; 
		for(int i=1;i<=k;++i) if(gcd(i,k)==1) ans=ans*i%k;
		ans=pw(ans,cnt,k);
		for(ll i=l+cnt*k;i<=r;++i) if(gcd(i%k,k)==1) ans=(ans*(i%k))%k; 
		printf("Case #%lld: %lld\n",++cns,ans%k);
	}
}

详情