LightOJ 1236 - Pairs Forming LCM (唯一分解定理)(最小公倍數)

題幹：

根據代碼輸出res的值。

long long pairsFormLCM( int n ) {
    long long res = 0;
    for( int i = 1; i <= n; i++ )
        for( int j = i; j <= n; j++ )
           if( lcm(i, j) == n ) res++; // lcm means least common multiple
    return res;
}
           

思路：

根據唯一分解定理，x= p 1 e 1 p1^{e1} p1e1 * p 2 e 2 p2^{e2} p2e2 * p 3 e 3 p3^{e3} p3e3 … p n e n pn^{en} pnen

是以，x的任意兩個因子a,b也可以分解為：

a= p 1 a 1 p1^{a1} p1a1 * p 2 a 2 p2^{a2} p2a2 * p 3 a 3 p3^{a3} p3a3 … p n a n pn^{an} pnan

b= p 1 b 1 p1^{b1} p1b1 * p 2 b 2 p2^{b2} p2b2 * p 3 b 3 p3^{b3} p3b3 … p n b n pn^{bn} pnbn

然後給出一種新的求最大公約數和最小公倍數的公式 (我現在還不會證明orz)

gcd(a,b)= p 1 m i n ( a 1 , b 1 ) p1 ^ {min(a1,b1) } p1min(a1,b1)* p 2 m i n ( a 2 , b 2 ) p2 ^ {min(a2,b2) } p2min(a2,b2) … p n m i n ( a n , b n ) pn ^ {min(an,bn) } pnmin(an,bn)

lcm(a,b)= p 1 m a x ( a 1 , b 1 ) p1 ^ {max(a1,b1) } p1max(a1,b1)* p 2 m a x ( a 2 , b 2 ) p2 ^ {max(a2,b2) } p2max(a2,b2) … p n m a x ( a n , b n ) pn ^ {max(an,bn) } pnmax(an,bn)

又因為要求是滿足lcm(a,b)=n的情況，也就是要求max(a1,b1)=e1。。。max(an,bn)=en，

也就是要求ai=ei或bi=ei或ai=bi=ei，

是以ai=ei時，bi ∈ \in ∈[0,ei]; bi=ei時，ai ∈ \in ∈[0,ei],

共有2*(ei+1)-1(ai=bi=ei多出現了一次)種情況。

#include <cstdio>  
#include <cstring>
#include <iostream>    
#include <algorithm>
#include <cmath>
using namespace std;
const int mx = 1e7+7;
bool f[mx];
int p[1100000],num;
void f1()
{
	for(int i=2;i<mx;i++){
		if(!f[i])  p[num++]=i;
		for(int j=0;j<num&&i*p[j]<mx;j++){
			f[i*p[j]]=true;
			if(!(i%p[j]))  break;
		}
	}
}
int main()
{
	int t;
	long long n;
	f1();
	scanf("%d",&t);
	for(int k=1;k<=t;k++){
		scanf("%lld",&n);
		int ans=1;
		for(int i=0;i<num&&p[i]*p[i]<=n;i++){
			int sum=0;
			while(n%p[i]==0)
			{
				sum++;
				n/=p[i];
			}
			if(sum)
				ans*=(2*sum+1);
		}
		if(n>1)
			ans*=3;
		printf("Case %d: %d\n",k,(ans+1)/2);
	}
	return 0;
}