Article From:https://www.cnblogs.com/ttttttttrx/p/9906610.html

How many different results of LCM (a, b)/a in B from 1-1e18 are given.

Ideas lcm*gcd=a*b to b/gcd(a,b)

That is to say, how many values of GCD (a, b) can be decomposed by the unique decomposition theorem, and then how many kinds of factors can be combined?

Note: Because the only decomposition laws are prime numbers, think about it and you can see that it is impossible to get the same result in two different combinations, so you can rest assured that it will work.

 

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000;
long long  prime[maxn],vis[maxn*10];
long long k=0;
void prime1(){
memset(vis,0,sizeof(vis));

for(long long i=2;i<=maxn;i++)if(!vis[i]){
	prime[k++]=i;
	for(long long j=i*i;j<=maxn;j+=i)vis[j]=1;
}
}
int main(){
long long b;
prime1();
cin>>b;
long long z=b;
long long ans=0;
long long sum=1;
for(long long  i=0;i<k&&prime[i]*prime[i]<=z;i++){
    ans=0;
	while(b%prime[i]==0){
      ans++;
	  b/=prime[i];
	}
	sum*=(ans+1);
}
if(b>1)sum*=(1+1);
cout<<sum<<endl;
	return 0;
}

  

Leave a Reply

Your email address will not be published. Required fields are marked *