反発定理njust 1923 triple

転送ドア:クリックしてリンクを開く
問題: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","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int MX = 1e5 + 5;

LL F[MX];
LL f(LL n) {
    return n * (n - 1) * (n - 2) / 6;
}
int main() {
    //FIN;
    int T, n, m;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        memset(F, 0, sizeof(F));
        for(int i = m; i <= n; i += m) {
            F[i] = f(n / i);
        }
        for(int i = n; i >= m; i--) {
            if(F[i]) {
                for(int j = i * 2; j <= n; j += i) {
                    F[i] -= F[j];
                }
            }
        }
        printf("%lld
", F[m]);
    }
    return 0;
}