当前位置：首页 > news >正文

打卡信奥刷题（3284）用C++实现信奥题 P8926 「GMOI R1-T3」Number Pair

news 2026/6/4 18:15:31

P8926 「GMOI R1-T3」Number Pair

题目描述

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

k×gcd⁡(x,y)=lcm⁡(x,y)k \times \gcd(x,y)=\operatorname{lcm}(x,y)k×gcd(x,y)=lcm(x,y)并且P≤gcd⁡(x,y)≤QP \le \gcd(x,y) \le QP≤gcd(x,y)≤Q（保证P≤QP \le QP≤Q）。

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

答案对109+710^9+7109+7取模。

输入格式

本题有多组数据。

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

接下来TTT行，每行三个整数k,P,Qk,P,Qk,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%100\%100%的数据1≤k≤10161 \le k \le 10^{16}1≤k≤1016，1≤T≤501 \le T \le 501≤T≤50，1≤P≤Q≤2×1091 \le P \le Q \le 2\times 10^91≤P≤Q≤2×109。

测试点	kkk	TTT	PPP	QQQ	总分
1∼31\sim 31∼3	k≤3k \le 3k≤3	T=1T=1T=1	P=1P=1P=1	Q=1Q=1Q=1	151515
4∼84\sim 84∼8	k≤100k \le 100k≤100	T≤8T \le 8T≤8	P≤30P \le 30P≤30	Q≤30Q \le 30Q≤30	151515
9∼139\sim 139∼13	k≤103k \le 10^3k≤103	T≤50T \le 50T≤50	P≤500P \le 500P≤500	Q≤500Q \le 500Q≤500	252525
14∼1814\sim 1814∼18	k≤1012k \le 10^{12}k≤1012	T≤50T \le 50T≤50	P≤104P \le 10^4P≤104	Q≤104Q \le 10^4Q≤104	151515
19∼2219\sim 2219∼22	k≤1013k \le 10^{13}k≤1013	T≤50T \le 50T≤50	P≤106P \le 10^6P≤106	Q≤106Q \le 10^6Q≤106	121212
23∼2823\sim 2823∼28	k≤1016k \le 10^{16}k≤1016	T≤50T \le 50T≤50	P≤2×109P \le 2\times10^9P≤2×109	Q≤2×109Q \le 2\times10^9Q≤2×109	181818

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

C++实现

#include<bits/stdc++.h>usingnamespacestd;intconstN=6e6+10;intcnt,prime[N];longlongconstmod=1e9+7;bitset<100000001>vis;inlinelonglongqpow(longlonga,longlongb,longlongt=1){for(;b;b>>=1,a=a*a%mod)if(b&1)t=t*a%mod;returnt;}inlinevoidwork(intn){for(inti=2;i<=n;++i){if(!vis[i])prime[++cnt]=i;for(intj=1;j<=cnt&&i*prime[j]<=n;++j){vis[i*prime[j]]=1;if(i%prime[j]==0)break;}}}signedmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);intt;cin>>t;work(100000000);while(t--){longlongans=0,k,p,q;cin>>k>>p>>q;for(inti=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';}return0;}