Codeforces Round #518 (Div. 2)B LCM

xiaoxiao2025-06-11  30

题目

题意:

a的取值范围为1到10的18次方,b的取值范围为1到10的10次方,给出b的值,求lcm(a,b)/a有多少个不同的值。

思路:

lcm(a,b)/b-->a*b/(gcd(a,b)*a)-->b/gcd(a,b);因为a可以取到10的18次方,所以只要求出1到b能被b整除的数的个数就好了。比如b的一个因子为3,a可以取3000,333333,30000000000都行,只要是3的倍数,所以b中的因子肯定能被全部取到。

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll b; cin>>b; ll ans=0; for(ll i=1;i*i<=b;i++) { if(i*i==b) { ans+=1; break; } if(b%i==0) ans+=2; } cout<<ans<<endl; return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-5031649.html

最新回复(0)