题意:
给定b,求lcm(a,b)/a 有多少种,1<=a<=b<=1e11
解:
首先:lcm(a,b)/a=a*b/(gcd(a,b)*a)=b/gcd(a,b)
其次,若 b%a!=0,则b/gcd(a,b)=b/1=b,a不贡献
那么 问题就转化为了b的因子有多少种。
首先,O(n)的试除法是不能通过题目的
那么我们是否可以转化为O(sqrt(n))的试除法呢,也就是只求b的素因子呢?
考虑例子:b=120=2^3*3*5
转化为组合问题:2有3个,3有1个,5有1个,会有几种不同的组合呢?
对于一个数,我们有选几个与不选,显然每个数的可能性为数的个数+1(不选)
其中,都不选=1,都选=120=b
由乘法原理:ans=4*2*2=16
这样做是正确的。
#include <iostream> #include <vector> #include <utility> using namespace std; typedef long long ll; ll solve(ll x) { ll ans = 1, res; for (ll i = 2; i * i <= x; i++) { res = 1; while (x % i == 0) { x /= i; ++res; } ans*=res; } if (x > 1)ans*=2; return ans; } int main() { ll b; cin >> b; cout<<solve(b)<<"\n"; return 0; }
标签:LCM,gcd,CF1068B,ll,不选,long,ans,include From: https://www.cnblogs.com/FeiShi/p/16664541.html