【Mail.Ru Cup 2018 Round 3 B. Divide Candies】分析+暴力

B. Divide Candies

题意

给你一个n*n的方格，点(i,j)的权值为$i^2+j^2$
问这个方格内有多少个数是m的倍数
$1<=n<=10^9,1<=m<=1000$

做法

$由于m的数据范围很小，我们可以直接算出m?m之内的是m的倍数的个数$
$如果把m?m这个矩形内的所有点的横坐标+m，m的倍数的个数还是不变的$
$纵坐标同理，于是我们算出n?n中包含多少个m?m,之后同理再算剩下的小块$
$复杂度O(nlogn)$

如上图蓝色阴影用蓝色块翻倍算，红色阴影用红色块翻倍算，紫色块自己算
代码

#include<stdio.h>
typedef long long ll;
int main()
{
    ll n,m;scanf("%lld%lld",&n,&m);ll cnt=0;for(ll i=1;i<=m;i++){
    for(ll j=1;j<=m;j++){
    ll tmp=i*i+j*j;if(tmp%m==0) cnt++;}}ll ans=((n/m)*(n/m))*cnt;cnt=0;for(ll i=(n-n%m)+1;i<=n;i++){
    for(ll j=1;j<=m;j++){
    ll tmp=i*i+j*j;if(tmp%m==0) cnt++;}}ans+=2LL*cnt*(n/m);cnt=0;for(ll i=(n-n%m)+1;i<=n;i++){
    for(ll j=(n-n%m)+1;j<=n;j++){
    ll tmp=i*i+j*j;if(tmp%m==0) cnt++;}}ans+=cnt;printf("%lld\n",ans);return 0;
}