题意:
就是求1-n中有多少对i 和 j 的最小公倍数为n (i <= j)
解析:
而这题,我们假设( a , b ) = n ,那么:
n=pk11pk22⋯pkss,
a=pd11pd22⋯pdss, b=pe11pe22⋯pess,
可以确定max(ei,di)=ki, 关于这点 可以自己反证一下
那么ki的组成就是ei与di中一个等于ki,
另一个任取[0,ki-1]中的一个数,
那么就有 2ki 种方案,
由于 ei=di=ki 只有一种,(两种都为ki)
所以第i位方案数为2ki+1,
有序对(a,b)方案数就是(2k1+1)(2k2+1)⋯(2ks+1),
无序对(a,b)方案数就是:{[(2k1+1)(2k2+1)⋯(2ks+1)] + 1}/2
(n,n)已经只有一个,不会重复,所以+1 再除 2。
题解转载至:https://blog.csdn.net/qq_15714857/article/details/48641121
代码:
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define maxn 10000900
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int LL_INF = 0x7fffffffffffffff,INF = 0x3f3f3f3f;
LL primes[maxn/];
bool vis[maxn];
LL ans = ;
void init()
{
mem(vis,);
for(int i=; i<maxn; i++)
if(!vis[i])
{
primes[ans++] = i;
for(LL j=(LL)i*i; j<maxn; j+=i)
vis[j] = ;
}
} int main()
{
init();
int T;
int kase = ;
cin>> T;
while(T--)
{
LL n, res = , cnt = ;
cin>> n;
for(LL i=; i<ans && primes[i] * primes[i] <= n; i++)
{
LL cnt2 = ;
while(n % primes[i] == )
{
n /= primes[i];
cnt2++;
}
if(cnt2 > )
{
res *= (*cnt2 + );
}
}
if(n > )
{
res *= ;
}
printf("Case %d: %lld\n",++kase,res/+);
}
return ;
}