CodeForces - 1068BLCM (数论)

xiaoxiao2025-11-01  20

题目大意:

       读入一个b,a从1-1e18 循环,求有多少个不同的值

题解:

      开始一看是div2的B题,并且过的人数比A题还要多,就知道这题肯定是不难

      思路是,将lcm转换成gcd。  于是

       gcd(a,b)肯定是b的因子,既然a是1-1e18,那么肯定所有情况都能够枚举到,所以gcd(a,b)能够取遍b的所有因子,

所以 的个数就是b的因子个数

 

      注意这个最后在判断i*i=b时可能会爆int,要开到long long,一度入了这个坑。。。。。

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

 

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

最新回复(0)