南阳理工学院ACM多乐赛暨16级退役纪念赛　I 成对最小公倍数

题目来源:http://acm.nyist.edu.cn/problem/1669

题目描述:

做水题就是在浪费时间，但是一场比赛要是没有送分的签到题，大家的比赛体验就会很差。为了优化你的比赛体验又不浪费你的读题时间，我并不打算给你很复杂的故事背景，你只需要复制下面的代码并选择正确的语言提交即可通过此题。

int superLCM( int n ) {
   int res = 0;
    for( int i = 1; i <= n; i++ )
        for( int j = i; j <= n; j++ )
           if( lcm(i, j) == n ) res++; // lcm是i和j的最小共倍数
    return res;
}

给你一个n,求superLCM(n)的值。

输入描述:

输入以整数T(T <= 200)开始，表示测试用例的数量。
每种情况都从包含整数n(1≤n≤10^6)的一行开始。

输出描述:

对于每个测试，每行打印函数superLCM( int n )返回的值。

样例输入:

15
2
3
4
6
8
10
12
15
18
20
21
24
25
27
29

样例输出:

2
2
3
5
4
5
8
5
8
8
5
11
3
4
2

1e6的解法：
直接枚举他的因子子
1e14的解法：（待更新
分解质因子子。求出每个素因子子的个数xi,然后t=(2x1+1)…(2*xi+1),然后i=j只有一一种所以i < j
的有(t-1)/2所以加上i=j的(t+1)/2就是答案。

注意ll详细看代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define ll long long
const int N=1e6+5;
#define inf 0x3f3f3f3f
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
ll yin_zi[N],n,top;
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
map<ll,ll>vis;
void init()
{
    top=0;
    for(int i=1;i<=n;i++){
        if (n%i==0){
            yin_zi[top++]=i;
        }
    }
}
void sovle(){
    ll ans=0;
    for(ll i=0;i<top;i++){
        for(ll j=i;j<top;j++){
            if(((yin_zi[i]*yin_zi[j])/gcd(yin_zi[i],yin_zi[j]))==n) {
                //cout<<"i "<<yin_zi[i]<<" j "<<yin_zi[j]<<endl;
                ans++;
            }
        }
    }
    vis[n]=ans;
    printf("%lld\n",ans);
}
int main(){
    ll t;
    scanf("%lld",&t);
    while (t--){
        mem(yin_zi,0);
        scanf("%lld",&n);
        if (vis[n]){
            printf("%d\n",vis[n]);
        }
        else {
            init();
            sovle();
        }
    }
    return 0;
}