B. Divide Candies

• Quiz
  • https://codeforces.com/problemset/problem/1056/B
• AC
  • https://codeforces.com/contest/1056/submission/89797233
• 解説
  • mが小さく、m x mの範囲なら全探索できる。その中で条件を満たす座標を見つけた時、それに対応する座標がm x mより向こうの範囲に何個あるかを考えればいい
  • O(m²)

sample 2 (n=6, m=5)

int main(){
    // input
    ll n,m;cin>>n>>m;
    
    ll sum=0;
    FOR(y,1,m+1){
      FOR(x,1,m+1){
        ll a = x*x+y*y;
        if(a%m==0){
          if(x<=n && y<=n){
            // いくつあるか？
            ll y_num = (n-y+1+m-1)/m;
            ll x_num = (n-x+1+m-1)/m;
            sum += y_num * x_num;
          }
        }
      }
    }
    p(sum);

    return 0;
}