A题题解

MCRS_lizi · 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;
}
//抄袭题解这个习惯不好哦