C++14(g++5.4) 解法, 执行用时: 1436ms, 内存消耗: 4452K, 提交时间: 2019-02-28 09:43:26

/*
题意定简单的, 就是需要扩展crt合并一下

*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#define ll long long
#define LL long long
#define M 1000100
#define mmp make_pair
using namespace std;
int read() {
	int nm = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
	return nm * f;
}

int poww(int a, int b, int mod) {
	int ans = 1, tmp = a;
	for(; b; b >>= 1, tmp = 1ll * tmp * tmp % mod) if(b & 1) ans = 1ll * ans * tmp %mod;
	return ans;
}
int p[44], cnt[44], pq[44], f[M], tot, n, m, k, ans;

int main() {
	n = read() & (~1), m = read(), k = read();
	int now = k;
	for(int i = 2; i * i  <=  now; i++) {
		if(now % i == 0) {
			p[tot] = i, pq[tot] = 1;
			cnt[tot] = 0;
			while(now % i == 0) cnt[tot]++, pq[tot] *= i, now /= i;
			tot++;
		}
	}
	if(now > 1) p[tot] = pq[tot] = now, cnt[tot] = 1, tot++;
	for (int nzz=0; nzz<tot; nzz++) {
		int mod = pq[nzz], phi = mod/p[nzz]*(p[nzz]-1);
		int pre=1,ct=0;
		for (int i=0,sz=min(m+cnt[nzz],n+1); i<=sz; i++) {
			int tmp1=n+2-i,cnt1=0,tmp2=i+1,cnt2=0;
			while (tmp1%p[nzz]==0) tmp1/=p[nzz], cnt1++;
			while (tmp2%p[nzz]==0) tmp2/=p[nzz], cnt2++;
			pre = pre*(LL)tmp1%mod*poww(tmp2,phi-1,mod)%mod;
			ct = ct+cnt1-cnt2;
			if (ct >= cnt[nzz]) f[i]=0;
			else f[i] = pre*(LL)poww(p[nzz],ct,mod)%mod;
		}
		int ret=0;
		if (p[nzz]==2) {
			for (int i=0; i<=m; i+=2) {
				int d=0;
				for (int j=i+1,tmp=1; tmp; j++) {
					d=(d+tmp*(LL)f[j])%mod;
					tmp=tmp*(LL)(mod-2)%mod;
				}
				ret = (ret+d)%mod;
			}
		} else {
			LL inv2 = poww(2,phi-1,mod);
			int d = f[0]*inv2%mod;
			ret = (ret+d)%mod;
			for (int i=1; i<=m; i++) {
				d = (f[i]-d+mod)*inv2%mod;
				if (i%2==0) ret = (ret+d)%mod;
			}
		}
		ans = (ans + ret*(LL)(k/mod)%k*poww(k/mod,phi-1,mod))%k;
	}
	cout << ans << "\n";
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1454ms, 内存消耗: 43484K, 提交时间: 2018-08-12 18:39:14

//by yjz
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll x,ll k,ll md){return k==0?1:1ll*qpow(1ll*x*x%md,k>>1,md)*(k&1?x:1)%md;}
int N,M,K,X,cnt[33],a[1001111],b[1001111];
int phi;
const int B=1001111;
int pr[15],pk[15],pn,tab[15][B];
void fac(int K)
{
	int OK=K;
	phi=K;
	for(int i=2;i*i<=K;i++)
	{
		if(K%i==0)
		{
			phi=phi/i*(i-1);
			while(K%i==0)K/=i,pk[pn]++;
			pr[pn++]=i;
		}
	}
	if(K>1)
	{
		phi=phi/K*(K-1);
		pk[pn]=1;
		pr[pn++]=K;
	}
	for(int i=0;i<pn;i++)
	{
		tab[i][0]=1;
		for(int j=1;j<B;j++)tab[i][j]=1ll*tab[i][j-1]*pr[i]%OK;
	}
}
void mul(int x)
{
	for(int i=0;i<pn;i++)
	{
		while(x%pr[i]==0)
		{
			x/=pr[i];
			cnt[i]++;
		}
	}
	X=1ll*X*x%K;
}
void div(int x)
{
	if(X==0)return;
	for(int i=0;i<pn;i++)
	{
		while(x%pr[i]==0)
		{
			x/=pr[i];
			cnt[i]--;
		}
	}
	if(x>1)X=1ll*X*qpow(x,phi-1,K)%K;
}
int query()
{
	int ret=X;
	for(int i=0;i<pn;i++)
	{
		assert(cnt[i]<B);
		ret=1ll*ret*tab[i][cnt[i]]%K;
	}
	return ret;
}
int calc(int K)
{
	int inv2=(K+1)/2;
	b[0]=1ll*a[0]*inv2%K;
	for(int i=1;i<=2*M;i++)
	{
		b[i]=1ll*(a[i]-b[i-1])*inv2%K;
	}
	ll ret=0;
	for(int i=0;i<=M;i++)ret+=b[i*2];
	return (ret%K+K)%K;
}
int calc2(int K)
{
	for(int i=2*M+32;i>=0;i--)
	{
		b[i-1]=(a[i]-2ll*b[i])%K;
	}
	ll ret=0;
	for(int i=0;i<=M;i++)ret+=b[i*2];
	return (ret%K+K)%K;
}
int main()
{
	cin>>N>>M>>K;
	N=N/2+1;M=M/2;
	fac(K);
	X=1;
	for(int i=1;i<=2*M+32;i++)
	{
		if(2*N-i+1==0)break;
		mul(2*N-i+1);
		div(i);
		a[i-1]=query();
	}
	int d=0;
	if(pn>0&&pr[0]==2)d=pk[0];
	int K1=K/(1<<d),ans1=calc(K1);
	int K2=1<<d,ans2=calc2(K2);
	if(K1>K2)
	{
		swap(K1,K2);swap(ans1,ans2);
	}
	for(int i=0;i<K1;i++)
	{
		if((i*K2+ans2)%K1==ans1)
		{
			cout<<i*K2+ans2<<endl;
			return 0;
		}
	}
	return 0;
}