有这样一个有关最大公约数的函数:
函数 f(x, y):
{
c=0
当 y>0:
{
c +=1
t = x % y
x = y
y = t
}
返回 c * x * x
}
给出三个正整数n,m,p，你需要计算:
∑i=1n∑j=1m⌊i∗jf(i,j)
对p取模的结果。
#include <stdio.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <cctype>
using namespace std;
typedef long long ll;
void in(int& n){scanf("%d",&n);}
void in(ll& n){scanf("%I64d",&n);}
const int N = ;
int gcd[N][N],num[N][N];
int n,m,p;
ll calc(ll x,ll y,ll tot,ll cnt)//tot 个数 cnt 分母
{
ll ans = (tot+)*(x*y)+(tot+)*tot/*(y*y);//总和
ll rd = y*y%cnt;
ll ra = y*x%cnt;
ll res = ; //余数
/*for(int i=0;i<=tot;++i){res+=(i*rd+ra)%cnt;}
return (ans-res)/cnt%p;
*/ //复杂度太高
for(int i=;i<cnt;++i){
res += (rd*i+ra)%cnt;
}
res = tot/cnt*res;
for(int i=;i<=tot%cnt;++i)
{
res += (rd*i+ra)%cnt;
}
return (ans-res)/cnt%p;
}
void init()
{
for(int i=;i<N;i++)
for(int j=;j<N;j++)
if(i==||j==) gcd[i][j]=i+j;
else if(i<j) gcd[i][j] = gcd[i][j%i];
else gcd[i][j] = gcd[i%j][j];
for(int i=;i<N;i++)
for(int j=;j<i;j++)
{
if(j==) num[i][j] = ;
else num[i][j] = num[j][i%j] +;
}
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--)
{
int ans = ;
scanf("%d%d%d",&n,&m,&p);
for(int i=;i<=m;i++)
for(int j=;j<i&&j<=n;j++)
{
ans+=calc(j/gcd[i][j],i/gcd[i][j],(n-j)/i,num[i][j]);
ans%=p;
}
printf("%d\n",ans);
}
return ;
}
AC代码
因为计算被m限制 变成了m个等差数列 求数列每一项/cnt 之和
但是 但是 裸计算余数复杂度太大
所以 就是现场 看懂了题。。。也A不掉。。。。然后贴的这个余数 转化为cnt的计算方式。。。
肯定是以cnt长度为循环。。。tot/cnt个循环
余下的tot%cnt 再求一次即可
那么复杂度就降下来了