题目大意
给定一个N*M的网格。对一个顶点为格点的正方形R(不一定与格线平行),计算出其中有多少个单位格被R完全包含(记作F(R))。求所有正方形的F(R)之和。
题解
首先画一个“勾股图”:
粉色是我们的正方形(不和格线平行),设其外接正方形的边长为L,四周直角三角形的短边为a,则长边为L-a。设其中完整包含了F(L,a)个单位格。
我们这么计算第二部分:一红一白两个直角三角形拼成的矩形内有(L-a)*a个单位格,而对角线穿过了L-gcd(L,a)格,再除以2,就得到了一个三角形内的单位格数。将其乘以4,总共加起来得到:
没错,“斜线下方的格点数”没有简单公式,但“单位格数”有!
可以发现,F(L,a)即使当a>L-a时也成立,所以我们可以直接用a枚举到底,整道题目的答案就是:
这分成两部分:第一部分是一个关于L的多项式,第二部分是gcd(L,a)的前缀和。
至于怎么得到这个多项式呢,如果你数学好可以手推……作为一名数学技能荒废一年的咸鱼选手,我就直接用vector当低配版多项式类,让电脑推了……
前者很简单:L不超过10^6,暴力递推即可。后者也差不多,只需要先递推出来phi函数,然后枚举gcd(a,L)的值,就可以把Σgcd的表都打出来,详见代码。
代码
#include#include #include #include #include using namespace std; typedef long long LL; typedef vector Poly; const LL MOD=1000000007; const int H=6; LL gcd(LL a,LL b){ return !b?a:gcd(b,a%b); } LL lcm(LL a,LL b){ return a*b/gcd(a,b); } LL quickpow(LL a,LL n){ LL ans=1; while(n){ if(n&1) ans=(ans*a)%MOD; a=(a*a)%MOD; n>>=1; } return ans; } LL inverse(LL a){ return quickpow(a,MOD-2); } void print(Poly a){ for(int i=0;i M) swap(N,M); //N是较小者 A[0]=M+1,A[1]=-1;Poly D(A,A+2); A[0]=N+1,A[1]=-1;D=D*Poly(A,A+2); Poly F=give_Fsum_L(); Poly F1=D*F; LL ans=0; ans+=calc_presum_with(F1,P[N]); ans%=MOD; A[0]=2; Poly F2=D*Poly(A,A+1); ans+=calc_presum_with(F2,PG[N]); ans%=MOD; ans=(ans+MOD)%MOD; printf("%I64d\n",ans); } void prepare(void){ for(int i=1;i