当前位置: 代码迷 >> 综合 >> 容斥定理 njust1923 triple
  详细解决方案

容斥定理 njust1923 triple

热度:27   发布时间:2023-12-14 03:13:28.0

传送门:点击打开链接

题意:给n,m,求1~n中选3个不相等的数出来,3个数的最大公约数等于m的组合数有多少。(n, m <= 1e5)

思路:我们很容易通过组合,可以求出,3个数的最大公约数是i的倍数的组合数,即C(n/i, 3)

但是,我们需要的是最大公约数是m的组合数,所以我们先通过求出m的倍数的,然后把其他倍数的个数减去就行了

所以我们倒着做就ok了,复杂度O(nlogn)

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt",&#