每日一题Reverse Card (Easy Version)

文章目录

• • 题名：
  • 题意：
  • 题解：
  • 代码：

题名：

Reverse Card (Easy Version)

题意：

给定 n n n， m m m，存在 1 < = a < = n 1<=a<=n 1<=a<=n， 1 < = b < = m 1<=b<=m 1<=b<=m，使得 a + b a+b a+b是 b ⋅ g c d ( a , b ) b⋅gcd(a,b) b⋅gcd(a,b)的倍数。输出存在多少对 a a a， b b b。

题解：

因为 g c d ( a , b ) gcd(a,b) gcd(a,b)给正整数，所以 b ⋅ g c d ( a , b ) b⋅gcd(a,b) b⋅gcd(a,b)是 b b b的整数倍，所以要想 a + b a+b a+b为 b ⋅ g c d ( a , b ) b⋅gcd(a,b) b⋅gcd(a,b)的整数倍，则 a a a为 b b b的整数倍， g c d ( a , b ) = b gcd(a,b)=b gcd(a,b)=b，所以只需要满足 a + b = b ∗ b a+b=b*b a+b=b∗b，因此遍历 b b b,则对于每个 b b b，存在 （ n + b ） / （ b ∗ b ） （n+b）/（b*b） （n+b）/（b∗b）个 a a a可以与其匹配。

代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>

#define int long long

using namespace std;

const int N=2e5+10;
int a[N];

void solve(){
	int n,m;
	int ans=0;
	
	cin>>n>>m;
	
	for(int b=2;b<=m;b++) ans+=(n+b)/(b*b);
	cout<<ans+n<<endl;	
}
signed main(){
	int t;
	
	cin>>t;
	
	while(t--) solve();
	
	return 0;
}