G - Pairs Forming LCM LightOJ - 1236 （质因子分解）

题解：这道题要从n的角度来考虑i和j。

n可以表示为n=a1^p1*a2^p2*a3^p3......。n=lcm(i,j)，那么质因子a1^p1，a1可以在i或者j中，并且p1=max(a1i,a1j)即pi为i中ai和j中ai的最大值。假设a1在i中，对于质因子a1，b中有[0,p1]，一共有p1+1中选择。

a1在j中同理，a也有p1+1中选择。所以一共有2(p1+1)-1种情况。为什么要减去1呢?如果i中有p1个a1,b中也有p1个a1,这种情况我们算了两次。所以要减去1。然后累乘。这样算出来我们可以得到(i,j)和（j,i）的总数目。

所以应该除以2，如果i和j相等呢？我们除以2，把(i=n,j=n)这种情况除去了，所以应该再加1.

code:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

const ll N = 1E6 + ;

const ll MAX = 1e7;

ll pre[N];

bool prime[MAX+];

ll pos = ;

void inint(){

    prime[] = ;

    for (ll i = ; i <= MAX; i++) {

        if (!prime[i]) pre[++pos] = i;

        for (ll j = ; j <= pos && i * pre[j] <= MAX; j++) {

            prime[i * pre[j]] = ;

            if (i % pre[j] == ) break;

        }

    }

}

void solve(ll time){

    ll n;

    scanf("%lld",&n);

    ll n1 = n;

    ll ans=;

    for (ll i = ; i <= pos; i++) {

        if (pre[i] > n1) break;

        if (n1 % pre[i] == ){

            ll p=;

            while (n1 % pre[i] == ) {

                n1 /= pre[i];p++;

            }

            ans*=((ll)+*p);

        }

    }

    if (n1 != ) ans*=(ll);

    printf("Case %d: %lld\n",time,ans/+(ll));

}

int main(){

    inint();

    int t;

    scanf("%d",&t);

    for(int i=;i<=t;i++) solve(i);

    return ;

}

巴特西

G - Pairs Forming LCM LightOJ - 1236 （质因子分解）

最新文章

热门文章