题目链接:http://lightoj.com/volume_showproblem.php?problem=1236
题意:给你一个数n,求有多少对(i, j)满足 LCM(i, j) = n, (i<=j), n <= 1e14;
之前做的那道LightOj 1215 中有说过:LCM(x, y) = ∏(所有质因子幂高的项之积);
那么本题就先把n分解质因子幂的形式,即 n = p1a1*p2a2*...*pkak;(pi为质数)
现在先不管i和j的大小,当 i 中包含因子p1a1时,j中可以包含p10|1|2|...|a1共有(a1+1)种可能,同样当j也有这种可能,所以共有2*(a1+1)
要减去 i 和 j 相等等于a1的时候;所以共有2*a1+1种,对于每个因子,都有这样的,所以连乘起来即可,除了i=j的情况每种情况都有两次,所以要/2+1;
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
typedef long long LL;
const int oo = 0xfffffff;
const int N = 1e7+;
const double eps = 1e-; bool f[N];///用int会MLE;
int p[N/], k = ; void Prime()
{
for(int i=; i<N; i++)
{
if(!f[i]) p[k++] = i;
for(int j=i; j<N; j+=i)
f[j] = true;
}
} int main()
{
Prime();
///printf("%d\n", k); int T, t = ; scanf("%d", &T); while(T--)
{
LL n; scanf("%lld", &n); LL ans = ; for(int i=; i<k&&(LL)p[i]*p[i]<=n; i++)
{
LL cnt = ;
while(n%p[i] == )
{
cnt ++;
n /= p[i];
}
if(!cnt) continue;
ans *= *cnt+;
} if(n > ) ans *= ; ans = ans/ + ; printf("Case %d: %lld\n", t++, ans);
}
return ;
}