题目链接
D
思路
这题目就是求a,b公约数的个数中互质的个数。
我们对a,b中做质因数分解，然后查找有多少个相同的质因数，就最多可以选几个了。
为什么这样是对的？因为选择的每个数都可以分解成质因数，要求他们互质的话也就是要求他们没有相同的质因子。然后我们就贪心的选择质数就好了。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| clude<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e6+10;
bool vis[maxn];
ll prime[maxn],cnt;
ll ans = 0;
void init()
{
for(int i=2;i<maxn;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
}
for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
void solve(ll x,ll y)
{
for(int i=0;i<cnt;i++)
{
if(x%prime[i]==0&&y%prime[i]==0)ans++;
while(x%prime[i]==0)x/=prime[i];
while(y%prime[i]==0)y/=prime[i];
}
if(x==y&&x!=1)ans++;
}
int main()
{
ll a,b;
init();
cin>>a>>b;
solve(a,b);
cout<<ans+1<<endl;
}
|