LightOJ 1236 Pairs Forming LCM

Description:

Find the result of the following code:

long long pairsFormLCM( int n ) {
    long long res = 0;
    for( int i = 1; i <= n; i++ )
        for( int j = i; j <= n; j++ )
           if( lcm(i, j) == n ) res++; // lcm means least common multiple
    return res;
}

A straight forward implementation of the code may time out. If you analyze the code, you will find that the code actually counts the number of pairs (i, j) for which lcm(i, j) = n and (i ≤ j).

Input:

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ $1 0^{14}$ ).

Output:

For each case, print the case number and the value returned by the function ‘pairsFormLCM(n)’.

Sample Input:

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

Sample Output:

Case 1: 2
Case 2: 2
Case 3: 3
Case 4: 5
Case 5: 4
Case 6: 5
Case 7: 8
Case 8: 5
Case 9: 8
Case 10: 8
Case 11: 5
Case 12: 11
Case 13: 3
Case 14: 4
Case 15: 2

题目链接

先对 $N, i, j$ 进行素因子分解

$N = p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times . . . \times p_{k}^{e_{k}}$

$i = p_{1}^{i_{1}} \times p_{2}^{i_{2}} \times . . . \times p_{k}^{i_{k}}$

$j = p_{1}^{j_{1}} \times p_{2}^{j_{2}} \times . . . \times p_{k}^{j_{k}}$

$∵ L C M (i, j) = N$

$∴ i_{x} < = e_{x}, j_{x} = e_{x}$ 或 $i_{x} = e_{x}, j_{x} < = e_{x}$

所以对于每一个 $i_{x} 和 j_{x}$ 有 $2 \times e_{x} + 1$ 种组合方式

这样可以算出所有 $i$ 和 $j$ 的组合方式有 $(2 \times e_{1} + 1) \times (2 \times e_{2} + 1) \times . . . \times (2 \times e_{k} + 1)$ 种

题目代码规定了 $i$ 和 $j$ 的大小关系，所以将算得结果 $+ 1) \times 2$ 即为最终结果

题目N的最大范围到 $1 0^{14}$ ，对于素数筛来说范围过大，所以素数只筛到 $\sqrt{1 0^{14}} = 1 0^{7}$ ，素因子分解后特判一下数据大小即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout << #x << "=" << x << endl;
#define ArrayDebug(x,i) cout << #x << "[" << i << "]=" << x[i] << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e7 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
	char c;
	int sgn;
	if (c = getchar(), c == EOF) {
		return 0;
	}
	while (c != '-' && (c < '0' || c > '9')) {
		c = getchar();
	}
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0' && c <= '9') {
		ret = ret * 10 + (c - '0');
	}
	ret *= sgn;
	return 1;
}
template <class T>
inline void out(T x) {
	if (x > 9) {
		out(x / 10);
	}
	putchar(x % 10 + '0');
}

bool IsPrime[maxn];
ll Prime[maxn / 10];
int tot;
vector<ll> ResolveAns;

void PrimeInit() {
	mem(IsPrime, 1);
	IsPrime[1] = 0;
	tot = 0;
	for (ll i = 2; i < maxn; ++i) {
		if (IsPrime[i]) {
			Prime[tot++] = i;
			for (ll j = i * i; j < maxn; j += i) {
				IsPrime[j] = 0;
			}
		}
	}
}

void Resolve(ll x) {
	ResolveAns.clear();
	int num = 0;
	while (x > 1 && Prime[num] * Prime[num] <= x && num < tot) {
		if (!(x % Prime[num])) {
			int cnt = 0;
			while (!(x % Prime[num])) {
				x /= Prime[num];
				cnt++;
			}
			ResolveAns.pb(cnt);
		}
		num++;
	}
	if (x > 1) {
		ResolveAns.pb(1);
	}
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	PrimeInit();
	ll T;
	read(T);
	for (ll Case = 1, N; Case <= T; ++Case) {
		read(N);
		Resolve(N);
		ll ans = 1;
		for (int i = 0; i < int(ResolveAns.size()); ++i) {
			ans *= ResolveAns[i] * 2 + 1;
		}
		ans = (ans + 1) / 2;
		printf("Case %lld: %lld\n", Case, ans);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}