本文主要是介绍成对最小公倍数~写题笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
你只需要复制下面的代码并选择正确的语言提交即可通过此题。
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
解题思路：
枚举n的所有因子 （lcm(i,j)==n; i，j 一定是n的因子）。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<math.h>
using namespace std;
const int MAXN = 1e6 + 9;
int a[MAXN];
int lcm(int i, int j)
{return (i / __gcd(i, j)) * j; //不要写成 (i * j / __gcd(i,j)) , (i * j) 如果太大，会超long long
}
int book[MAXN];
int t = 0;
void deal(int n) // 找 n的因子
{t = 1;int mid = sqrt(n);for(int i = 1; i <= mid; i++){if(n % i == 0){if(book[i] == 0){a[t++] = i;book[i] = 1;}if(book[n/i] == 0){a[t++] = n / i;book[n/i] = 1;}}}
}
int main()
{int T;cin >> T;while(T--){memset(a, 0, sizeof(a));memset(book , 0, sizeof(book));int n;cin >> n;deal(n) ;int ans = 0;for(int i = 1; i < t; i++) //枚举n的因子{for(int j = 1; j < t; j++){if(lcm(a[i],a[j]) == n){ans++;}}}cout << (ans + 1 ) / 2 << endl;}return 0;
}
这篇关于成对最小公倍数~写题笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
