Description：

长度为 $n$ 的序列，都是不超过 $m$ 的正整数，要求和是 $p$ 的倍数。至少有一个数是质数。求有多少个序列满足条件。

$1\leqslant n\leqslant 10^9,1\leqslant m\leqslant2\times 10^7,1\leqslant p\leqslant 100$

Solution：

显然是用所有的方案数减去不包含任何一个质数的方案数，第一个的生成函数就是 $[1,m]$ 中 $\%p$ 为这个数的个数，第二个要求必须是质数，然后把它们分别快速幂起来，用第一个 $0$ 位置上的值减去第二个 $0$ 位置上的值即可，由于 $p$ 很小所以不用 $FFT$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,p;

#define MAXM 20000010

bool isprime[MAXM];

int prime[MAXM],tot = 0;

#define MAXP 110

long long a[MAXP],b[MAXP],c[MAXP];

long long tmp[MAXP];

#define MOD 20170408

void power(long long a[],int k)

{

	memset(c,0,sizeof(c));

	c[0] = 1;

	while(k > 0)

	{

		if(k & 1)

		{

			memset(tmp,0,sizeof(tmp));

			for(int i = 0;i < p;++i)

				for(int j = 0;j < p;++j)

					tmp[(i + j) % p] = (tmp[(i + j) % p] + a[i] * c[j]) % MOD;

			for(int i = 0;i < p;++i)c[i] = tmp[i];

		}

		memset(tmp,0,sizeof(tmp));

		for(int i = 0;i < p;++i)

			for(int j = 0;j < p;++j)

				tmp[(i + j) % p] = (tmp[(i + j) % p] + a[i] * a[j]) % MOD;

		for(int i = 0;i < p;++i)a[i] = tmp[i];

		k = k >> 1;

	}

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&p);

	for(int i = 2;i <= m;++i)isprime[i] = true;

	for(int i = 2;i <= m;++i)

	{

		if(isprime[i])prime[++tot] = i;

		for(int j = 1;j <= tot && i * prime[j] <= m;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)break;

		}

	}

	for(int i = 1;i <= m;++i)++a[i % p];

	power(a,n);

	for(int i = 0;i < p;++i)a[i] = c[i];

	for(int i = 1;i <= m;++i)

	{

		if(!isprime[i])++b[i % p];

	}

	power(b,n);

	cout << (a[0] - c[0] + MOD) % MOD << endl;

	return 0;

}