C++14(g++5.4) 解法, 执行用时: 943ms, 内存消耗: 25464K, 提交时间: 2019-07-24 21:34:08

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<vector>
#include<unordered_map>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const ll MOD = 20170408;
const int MaxN = 2e7 + 40;
typedef struct
{
	int n, m, flag;
}hhh;
int pp;
//unordered_map<hhh,ll>mp;
unordered_map<int, ll>mp[105][2];
bool notp[MaxN];
int tot;
int prime[MaxN];
ll dfs(int n, int p, int flag)
{
	if (mp[p][flag][n])return mp[p][flag][n];
	if (n == 1)
	{
		return mp[p][flag][n];
	}

	ll ans = 0;
	int mid = n / 2;
	if (flag == 1)
	{
		for (int i = 0; i < pp; i++)
		{

			int j = (p - i+pp) % pp;
			ans = (ans + dfs(mid, i, 1) * dfs(n - mid, j, 0))%MOD;
			//printf(">>%d %d %d %lld\n",mid,i,1,dfs(mid,i,1));

			ans = (ans + dfs(mid, i, 0) * dfs(n - mid, j, 1))%MOD;
			ans = (ans + dfs(mid, i, 1) * dfs(n - mid, j, 1))%MOD;
		}
		mp[p][flag][n] = ans;
	}
	else
	{
		for (int i = 0; i < pp; i++)
		{
			int j = (p - i+pp) % pp;
			ans = (ans + dfs(mid, i, 0) * dfs(n - mid, j, 0))%MOD;

		}
		mp[p][flag][n] = ans;
	}
	//printf("%d %d %d %lld\n", n, p, flag, mp[p][flag][n]);
	return mp[p][flag][n];
}

int main()
{
	notp[1] = 1;
	for (ll i = 2; i < MaxN; i++) {
		if (notp[i] == 0) {
			prime[++tot] = i;
		}
		for (ll j = 1; j <= tot; j++) {
			if (i * prime[j] > MaxN)
				break;

			notp[i * prime[j]] = 1;

			if (i % prime[j] == 0)
				break;
		}
	}
	int n, m, p;
	//printf("%d %d %d\n",notp[3],notp[13],notp[1]);
	scanf("%d%d%d", &n, &m, &pp);
	for (int i = 1; i <= m; i++)
	{
		mp[i % pp][!notp[i]][1]++;
		//printf("%d %d %d\n", i % p, !notp[i], 1);
	}

	printf("%lld\n", dfs(n, 0, 1));
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 273ms, 内存消耗: 24824K, 提交时间: 2020-08-15 21:03:57

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 110
#define MAXM 2000010
#define MOD 20170408
using namespace std;
int n,m,p,k=0,prime[MAXM];
bool np[MAXM*10];
struct node{
	long long num[MAXN];
	node(){memset(num,0,sizeof(num));}
}one,two;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
void make(){
	np[0]=np[1]=true;
	for(int i=2;i<=m;i++){
		if(!np[i])prime[++k]=i;
		for(int j=1;j<=k&&(long long)prime[j]*i<=m;j++){
			np[prime[j]*i]=true;
			if(i%prime[j]==0)break;
		}
	}
	for(int i=1;i<=m;i++){
		one.num[i%p]++;
		if(np[i])two.num[i%p]++;
	}
}
node operator *(const node &x,const node &y){
	node ret;
	for(int i=0;i<p;i++)
	for(int j=0;j<p;j++)
	ret.num[(i+j)%p]=(ret.num[(i+j)%p]%MOD+x.num[i]%MOD*y.num[j]%MOD)%MOD;
	return ret;
}
node mexp(node base,int k){
	node ans=base;
	k--;
	while(k){
		if(k&1)ans=ans*base;
		base=base*base;
		k>>=1;
	}
	return ans;
}
int main(){
	n=read();m=read();p=read();
	make();
	one=mexp(one,n);
	two=mexp(two,n);
	long long ans=(one.num[0]-two.num[0]+MOD)%MOD;
	printf("%lld\n",ans);
	return 0;
}