Tachibana Kanade Loves Game 牛客练习赛43 容斥原理

题目链接：Tachibana Kanade Loves Game

当k+（n- n中是2~m倍数的个数）<q 输出QAQ

所以只要找到n中是2~m倍数的个数题目就可以解决。

2<=m<=20  但是可以排除一些数，比如6，如果x是2的倍数，那么x肯定是6的倍数，所以找到n中是m中素数的倍数个数就行，m的取值为a[]={2,3,5,7,11,13,17,19}。

然后用容斥原理解题。

kjj,今天数学老师讲了欧拉函数才懂这题；这题和用容斥原理证明欧拉函数的过程差不多。

n中a[i]倍数的个数为n/a[i]  ,

n-n中是2~m倍数的个数=n-(n/a[0]+n/a[1]+...+n/a[7])+ (n/(a[0]*a[1]+...+n/(a[7]*a[8])) - ...+*n/(a[0]*...*a[n])=n*(1-1/a[0])*....*(1-1/a[7])

欧拉函数推理：

欧拉函数：求的是n内与n互素数的个数，而我们这个题求的是n内与2~m内数互素 数的个数。

欧拉函数中的pi相当于此题中的 m的取值为2,3,5,7,11,13,17,19。

所以  n-n中是2~m倍数的个数=n*（1-1/p1）*（1-1/p2）...（1-1/pk）;

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[]={2,3,5,7,11,13,17,19};
int main()
{
    int t;
    scanf("%d", &t);
    ll k, q, n, m;
    while (t--)
    {
        scanf("%lld%lld%lld%lld", &k, &q, &n, &m);
        if (k==0)
            printf("QAQ\n");
        else
        {
        	
            ll ans = n;
            int cnt=8;
            for (int i=0; i<8 ; i++)
            	if(m<a[i]){
            		cnt=i;break;
				}
            for (int i=0; i<cnt ; i++)
                ans=ans*(a[i]-1)/a[i];
            if ( k+ans>q )
                printf("Yes\n");
            else
                printf("QAQ\n");
        }
    }
}