LightOJ1236 https://vjudge.net/problem/LightOJ-1236 Pairs Forming LCM
标签
前言
我的 csdn 和博客园是同步的, 欢迎来访 danzh - 博客园 https://www.cnblogs.com/danzh/ ~
简明题意
\[\sum_{i=1}^n\sum_{j=1}^n[lcm(i,j)=n]\]
思路
对 n 质因数分解,\(n=p_1^{c1}p_2^{c_2}...p_k^{c_k}\), 由 lcm 的定义可以知道, ij 中, 对于每一个 \(p_i\), 都应该有 \(max(c_1,c_2)=c\), 因此, 需要让 ij 中的一个为 c, 另一个任选, 这样就有 \(2c+1\) 种选法. 所以答案就应该是 \(\prod (2c_i+1)\).
答案需要 a<=b, 所以答案需要 / 2(且要向上取整)
注意事项
无
总结
无
AC 代码
- #include<cstdio>
- const int maxn = 1e7 + 10;
- bool no_prime[maxn];
- int prime[(int)7e5];
- int shai(int n)
- {
- int cnt = 0;
- no_prime[1] = 1;
- for (int i = 2; i <= n; i++)
- {
- if (!no_prime[i])
- prime[++cnt] = i;
- for (int j = 1; j <= cnt && prime[j] * i <= n; j++)
- {
- no_prime[prime[j] * i] = 1;
- if (i % prime[j] == 0) break;
- }
- }
- return cnt;
- }
- void solve()
- {
- int cnt = shai(maxn - 10);
- int t;
- scanf("%d", &t);
- for (int i = 1; i <= t; i++)
- {
- long long n, r;
- scanf("%lld", &n);
- r = n;
- long long ans = 1;
- for (int i = 1; i <= cnt && 1ll * prime[i] * prime[i] <= r && n != 1; i++)
- {
- int cnt = 0;
- while (n % prime[i] == 0)
- n /= prime[i], cnt++;
- ans *= (2 * cnt + 1);
- }
- if (n != 1)
- ans *= 3;
- printf("Case %d: %lld\n", i, (ans + 1) / 2);
- }
- }
- int main()
- {
- freopen("Testin.txt", "r", stdin);
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3172621.html