本文主要是介绍NJUST 1923 triple (莫比乌斯反演)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
triple
Time Limit: 3000MS
Memory Limit: 65536KB
Description
给出一个整数n，表示1，2，...，n。从这n个数中任意选择3个不同的数字x，y，z，问x，y，z的最大公约数等于m的方案有多少种？（注意：(1,2,3)，(1,3,2)，(2,1,3)，(2,3,1)，(3,1,2)，(3,2,1)属于同一种方案）
Input
第一行输入一个整数T（1 <= T <= 100），表示有T组数据，接下来T行，每行2个整数n, m（1 <= m <= n <= 10^5）
Output
输出一个整数表示答案
Sample Input
15 1
Sample Output
10
题目链接：https://icpc.njust.edu.cn/Problem/Local/1923/
题目分析：其实是裸的莫比乌斯反演吧。。。最大公约数为m，把每个数都除m，就是求最大公约数为1的方案了，上个板子即可
题目分析：其实是裸的莫比乌斯反演吧。。。最大公约数为m，把每个数都除m，就是求最大公约数为1的方案了，上个板子即可
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
using namespace std;
int const MAX = 1e5 + 5;
int mob[MAX], p[MAX], cnt[MAX], num[MAX];
bool prime[MAX];
int n, k;void Mobius()
{memset(prime, true, sizeof(prime));int pnum = 0;mob[1] = 1;for(int i = 2; i < MAX; i++){if(prime[i]){p[pnum ++] = i;mob[i] = -1;}for(int j = 0; j < pnum && i * p[j] < MAX; j++){prime[i * p[j]] = false;if(i % p[j] == 0){mob[i * p[j]] = 0;break;}mob[i * p[j]] = -mob[i];}}
}ll cal()
{for(int i = 1; i <= n; i++)for(int j = i; j <= n; j += i)num[i] += cnt[j];ll ans = 0;for(int i = 1; i <= n; i++){int x = num[i];if(x >= 3)ans += (ll) mob[i] * x * (x - 1) * (x - 2) / 6;}return ans;
}int main()
{Mobius();int T;scanf("%d", &T);while(T --){scanf("%d %d", &n, &k);if(n < 3){printf("0\n");continue;}memset(cnt, 0, sizeof(cnt));memset(num, 0, sizeof(num));for(int i = 1; i <= n; i++)if(i % k == 0)cnt[i / k] ++;cout << cal() << endl;}
}这篇关于NJUST 1923 triple (莫比乌斯反演)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
