loj1236（数学）

时间：2021-01-10 06:41:22

传送门：Pairs Forming LCM

题意：题意：问符合 lcm(i,j)=n (1<=i<=j<=n，1<=n<=10^14) 的 (i,j) 有多少对。

分析：求素数分解式，若xi是第i个素数的幂，那么对于这两个数中有一个的幂一定是xi，另一个随意，那么对于第i的素数的分配方案有(2*xi+1)种（即假设第一个数的幂是xi，另一个数的幂可以为0~xi共xi+1种；另一方面假设第二个数是xi，同理第一个数的幂的选择有xi+1种，这里排除幂都是xi的情况，对于某个素数pi，这两个数的幂的选择方案有2*xi+1种）。那么对于所有素数，共有∏(2*xi+1)种分配方案，由于要排除(a,b),(b,a)这种情况，在之前的计算中除了两个数都是n这种情况都有重复，答案则应该是(∏(2*xi+1)+1)/2

#pragma comment(linker,"/STACK:1024000000,1024000000")

#include <cstdio>

#include <cstring>

#include <string>

#include <cmath>

#include <limits.h>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <stack>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 100000000

#define inf 0x3f3f3f3f

#define eps 1e-6

#define N 10000000

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define PII pair<int,int>

using namespace std;

inline LL read()

{

    char ch=getchar();LL x=,f=;

    while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}

    while(ch<=''&&ch>=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

bool vis[N+];

int prime[],tot;

void init()

{

    memset(vis,false,sizeof(vis));

    tot=;

    for(int i=;i<=N;i++)

    {

        if(!vis[i])

        {

            prime[tot++]=i;

        }

        for(int j=;j<tot&&i*prime[j]<=N;j++)

        {

            vis[i*prime[j]]=true;

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

        }

    }

}

int main()

{

    LL n;

    int T,cas=;

    init();

    T=read();

    while(T--)

    {

       n=read();

       LL ans=;

       for(int i=;i<tot&&(LL)prime[i]*prime[i]<=n;i++)

       {

           if(n%prime[i]==)

           {

               LL x=;

               while(n%prime[i]==)

               {

                   x++;n/=prime[i];

               }

               ans*=(x*+);

           }

       }

       if(n>)ans*=;

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

    }

}

相关文章