P8926 「GMOI R1-T3」Number Pair

题目描述

我们定义满足如下条件的数对 $(x,y)$ 叫做奇妙数对：

$k\times \gcd (x,y)=\mathrm{lcm}(x,y)$ 并且 $P\le \gcd (x,y)\le Q$（保证 $P\le Q$）。

有 $T$ 组数据，对于每一组数据，给定 $k,P,Q$ 三个数，求符合条件的数对 $(x,y)$ 的对数。

答案对 $10^9+7$ 取模。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据数量。

接下来 $T$ 行，每行三个整数 $k,P,Q$。

输出格式

对于每一组数据，给出对应答案，每组数据一行。

输入输出样例 #1

输入 #1

5
10 1 3
30 1 5
997 24 35
34 39 99
210 1000 1001

输出 #1

12
40
24
244
32

说明/提示

注意并不寻常的时间限制。

对于 $100\%$ 的数据 $1\le k\le 10^{16}$，$1\le T\le 50$，$1\le P\le Q\le 2\times 10^9$。

本题保证 $k$ 随机生成，并不存在极限卡人数据，时限已经开到 std 两倍，请各位选手放心。

C++实现

#include<bits/stdc++.h>
using namespace std;
int const N=6e6+10;
int cnt,prime[N];
long long const mod=1e9+7;
bitset<100000001>vis;
inline long long qpow(long long a,long long b,long long t=1){
	for(;b;b>>=1,a=a*a%mod)if(b&1)t=t*a%mod;return t;
	}
inline void work(int n){
	for(int i=2;i<=n;++i){
		if (!vis[i]) prime[++cnt]=i;
		for (int j=1;j<=cnt && i*prime[j]<=n;++j){
			vis[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		} 
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;cin>>t;work(100000000);
	while (t--){
		long long ans=0,k,p,q;
		cin>>k>>p>>q;
		for (int i=1;i<=cnt && prime[i]*prime[i]<=k;++i){
			if (k%prime[i]==0) ++ans;
			while (k%prime[i]==0) k/=prime[i];
		}
		if (k!=1) ++ans;
		cout<<(q-p+1)*qpow(2,ans)%mod<<'\n';
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容