讲道理,这题和那题做出来我离Au就不远了....(差3分!)

考试的时候好sb啊..现在回想起来并不难弄..?

我在NOI上就思考到,23²=529>500

那么对于一个数x,一定能表示成一个质数p(或者1)和前8个质数的乘积的形式

例如 46 = 2 * 23

我们接下来3^8大暴力

我们可以发现,对于一个数,如果它是前8个质数乘起的,我们可以判定出它能不能被选(如果能,答案*2,如果不能..答案不变)

如果是p*前8个数,我们先看它能不能选,能选我们记录下来,考虑p及其倍数时候,如果第一个人选有多少可选,第二个人选有多少可选

我们可以发现,这个p的选择方案就是2^第一个人有多少可以选+2^第二个人有多少可以选-1

我们这么理解:第一个人选或不选他所有的,第二个人选或不选他所有的,分别是2的若干次方,至于-1就是..都不选的情况

那么,代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int prime[11]={2,3,5,7,11,13,17,19};
int primes[105];
bool is_prime(int x)
{
    int i;
    for (i=2;i*i<=x;i++)
    {
        if (x%i==0) return false;
    }
    return true;
}
int val[505];
int leave[505];
int cnt1[505],cnt2[505];
int power(int x,int y,int p)
{
    if (y==0) return 1;
    int t=power(x,y/2,p);
    t=(long long)t*t%p;
    if (y%2==1) t=(long long)t*x%p;
    return t;
}
int main()
{
    int n,p;
    scanf("%d%d",&n,&p);
    int i;
    int sum=0;
    for (i=23;i<=n;i++)
    {
        if (is_prime(i)) primes[sum++]=i;
    }
    for (i=2;i<=n;i++)
    {
        int j;
        int t=i;
        for (j=0;j<8;j++)
        {
            if (i%prime[j]==0)
            {
                val[i]^=(1<<j);
            }
            for (;t%prime[j]==0;) t/=prime[j];
        }
        leave[i]=t;
    }
    int j;
    int ans=0;
    for (i=0;i<(1<<8);i++)
    {
        for (j=0;j<(1<<8);j++)
        {
            if (i&j) continue;
            int k;
            int flag=1;
            for (k=0;k<8;k++)
            {
                if ((1<<k)&(i|j)) flag*=-1;
            }
            for (k=1;k<=n;k++)
            {
                cnt1[k]=0;
                cnt2[k]=0;
            }
            for (k=2;k<=n;k++)
            {
                if ((val[k]&i)==val[k]) cnt1[leave[k]]++;
                if ((val[k]&j)==val[k]) cnt2[leave[k]]++;
            }
            int anses=1;
            for (k=0;k<sum;k++)
            {
                anses=(long long)anses*((1<<cnt1[primes[k]])+(1<<cnt2[primes[k]])-1)%p;
            }
            anses=(long long)anses*power(2,cnt1[1]+cnt2[1],p)%p;
            ans+=anses*flag;
            ans%=p;
        }
    }
    printf("%d\n",(ans+p)%p);
    //system("pause");
    return 0;
}