[lcm本质] light oj 1236 Pairs Forming LCM

}

题意：

就是求1~n之间，两两最小公倍数等于n的个数。

思路：

设lcm(A,B)=M
设分解质因数之后：
A=x^a1+y^a2+z^a3+......
B=x^b1+y^b2+z^b3+......
M=x^c1+y^c2+z^c3+......
因为M是A和B的最小公倍数，所以对每个质因数都会有max(ai ，bi)=ci
比如设ci=2，那么就有以下几种情况：
ai=2 , bi=2　　　　ai=2 , bi=1　　　　ai=2 , bi=0
ai=1 , bi=2　　　　ai=0 , bi=2

所以对于每个ci，所能创造的数量就是2*ci-1，全部乘起来就是总数了。

代码：

#include"cstdio"
#include"cstring"
#include"cmath"
#include"cstdlib"
#include"algorithm"
#include"iostream"
#include"map"
#include"queue"
#define ll long long
using namespace std;
#define MAXN 10000007
bool mark[MAXN];
int ss[MAXN/10],sscnt;
void ssb()
{
    sscnt=0;
    memset(mark,false,sizeof(mark));
    mark[0]=mark[1]=true;
    for(int i=2; i<=MAXN; i++)
    {
        if(!mark[i])
        {
            for(int j=i+i; j<=MAXN; j+=i) mark[j]=true;
            ss[sscnt++]=i;
        }
    }
    return ;
}
int main()
{
    int t,cas=1;
    cin>>t;
    ssb();
    while(t--)
    {
        ll n;
        ll ans=1;
        scanf("%lld",&n);
        for(int i=0;i<sscnt;i++)
        {
            if((ll)ss[i]*ss[i]>n) break;
            if(n%ss[i]==0)
            {
                int tep=0;
                while(n%ss[i]==0)
                {
                    tep++;
                    n/=ss[i];
                }
                ans*=2*tep+1;
            }
        }
        if(n!=1) ans*=3;
        printf("Case %d: %lld\n",cas++,(ans+1)/2);
    }
    return 0;
}

[lcm本质] light oj 1236 Pairs Forming LCM

原文：http://blog.csdn.net/wdcjdtc/article/details/44653803