Thursday, October 10, 2019


LightOJ - 1236 - Pairs Forming LCM


Problem Link : http://lightoj.com/volume_showproblem.php?problem=1236

Idea :  Suppose x and y are two number and their LCM is n.

x= p1^a1*p2^a2*p3^a3......ps^a

y= p1^b1*p2^b2*p3^b3......ps^b3

n= p1^max(a1,b1)*p2^max(a2,b2)*p3^max(a3,b3)......ps^max(a3,b3)

The takes an ordered pair of numbers first. 1:ai=ci,bi=[0,ei] There are ei+1 species 2:bi=ci, Ai=[0,ei], and Ai==ci,bi==ci, the above appeared, so there is a 2*ei+1 species minus one. for unordered pairs, the Lcm (n,n) appears only once (EI==AI==BI) so the solution is: ((2*e1+1) * (2*e2+1) ... (2*es+1) +1)/2; for an example: n=2^3; when a1=3, b1=3,2,1,0; b1=3,a1=3,2,1,0; The considers the ordered pair time (3,3) to repeat once, so subtract one time. When multiple items are multiplied by the same time, use the multiplication rule.


Code First Then See Solution

Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 10000007
#define ll long long

bitset <mx>b;
vector <long long>v;

void seive()
{
    b.set();
    b[0]=b[1]=false;
    for(ll i=0;i<mx;i++)
    {
        if(b[i])
        {
            v.push_back(i);
            for(ll j=i*i;j<mx;j+=i)
                b[j]=false;
        }
    }
}

int main()
{
    int t,f=0;
    seive();
    cin>>t;
    while(t--)
    {
        f++;
        long long n,res=1;
        cin>>n;
        for(int i=0;i<v.size()&&v[i]<=n;i++)
        {
            if(n%v[i]==0)
            {
                int cnt=0;
                while(n%v[i]==0)
                {
                    cnt++;
                    n/=v[i];
                }
                res*=(2*cnt+1);
            }
        }
        if(n!=1)
            res*=(2*1+1);
        cout<<"Case "<<f<<": "<<res/2+1<<endl;
    }
    return 0;
}


No comments:

Post a Comment