LightOJ 1236 Pairs Forming LCM 合数分解

题意：求所有小于等于n的，x,y&&lcm(x,y)==n的个数

分析：因为n是最小公倍数，所以x,y都是n的因子，而且满足这样的因子必须保证互质，由于n=1e14,所以最多大概在2^13个因子即8000多因子

所以每次可以递归暴力寻找一个因子，然后选好了以后，看唯一分解不同种素数还有哪种没有用，符合条件的只能用这些没有用过的，然后直接统计

注：由于最终每个对都被统计了两次，所以/2，由于本身也算一对，所以+1

代码：

#include <cstdio>

#include <iostream>

#include <ctime>

#include <vector>

#include <cmath>

#include <map>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long LL;

const int N=1e7+;

const int INF=0x3f3f3f3f;

int cnt;

bool v[N];

LL prime[];

void getprime(){

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

    if(!v[i])

      for(int j=i*i;j<=N-;j+=i)

        v[j]=;

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

  if(!v[i])prime[++cnt]=i;

}

int ans;

vector<LL>g,c;

bool vis[];

void dfs(int pos,LL res){

  if(pos==g.size()){

    int tmp=;

    for(int i=;i<g.size();++i){

      if(vis[i])continue;

      tmp*=(c[i]+);

    }

    ans+=tmp;

    return;

  }

  dfs(pos+,res);

  vis[pos]=;

  for(LL i=,k=g[pos];i<=c[pos];++i,k*=g[pos])

    dfs(pos+,res*k);

  vis[pos]=;

  return;

}

int main()

{

    getprime();

    int cas=,T;

    scanf("%d",&T);

    while(T--){

      LL t,n;

      scanf("%lld",&n),t=n;

      g.clear(),c.clear();

      for(int i=;i<=cnt&&prime[i]*prime[i]<=t;++i){

          if(t%prime[i])continue;

          int tot=;

          g.push_back(prime[i]);

          while(t%prime[i]==)t/=prime[i],++tot;

          c.push_back(tot);

      }

      if(t>)g.push_back(t),c.push_back();

      ans=;

      dfs(,);

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

    }

    return ;

}

巴特西

LightOJ 1236 Pairs Forming LCM 合数分解

最新文章

热门文章