自动搬运

查看原文

来自洛谷，原作者为

	MCRS_lizi 神，不惧死亡！

搬运于2025-08-24 22:43:50，当前版本为作者最后更新于2022-12-11 10:13:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目意思已经很清楚了，直接讲解思路吧。

首先瞟一眼数据范围， $n,m\le10^{12}$ 决定了这题时间复杂度与 $n,m$ 有关的可能性不大，而 $p\le10^3$ 这个范围可以让我们大胆推断这题复杂度是 $O(p^2)$。

那具体如何实现呢？

对于 $i\bmod p$ 与 $j\bmod p$ 的结果而言，组合起来一共只有 $p^2$ 种情况，意思是我们可以求出满足这两个式子为某个结果时的情况总数，再两两组合，将第一个式子情况数乘上第二个式子情况数，再乘上组合后对应的结果即可。

那么还有个要将解决的问题，这个情况总数该如何求取？

经过思考，我们不难发现每一种可能的值至少有 $\left \lfloor \dfrac{n}{p} \right \rfloor$ 以及 $\left \lfloor \dfrac{m}{p} \right \rfloor$ 种情况，最后再根据枚举的结果为多少确定这个情况数是否要加一（判断方式是枚举的结果数值加上刚刚算出来至少情况数乘以 $p$ 是否小于等于 $n$ 或 $m$）。

这样子这题就算解决了。

多一嘴，别忘了开 long long。

CODE：

#include<bits/stdc++.h>
#define int long long//不开longlong见祖宗
using namespace std;
const int mod=1e9+7;
int n,m,p,f[1010][1010],cnt1[1010],cnt2[1010],ans;
signed main()
{
	cin>>n>>m>>p;
	for(int i=0;i<p;i++)
	{
		for(int j=0;j<p;j++)
		{
			f[i][j]=i*j%p;//先预处理一下结果，其实不处理也没关系，不过这样后面代码会不那么shishan
		}
	}
	for(int i=0;i<p;i++)
	{
		cnt1[i]+=n/p%mod,cnt2[i]+=m/p%mod;
		if(n/p*p+i<=n)
		{
			cnt1[i]++;
		}
		if(m/p*p+i<=m)
		{
			cnt2[i]++;
		}//情况统计，理由见上方
	}
	for(int i=0;i<p;i++)
	{
		for(int j=0;j<p;j++)
		{
			ans+=cnt1[i]*cnt2[j]%mod*f[i][j]%mod;//针对每种情况乘以结果
		}
	}
	cout<<ans%mod;
 	return 0;
}
//抄袭题解这个习惯不好哦