naoya_t@hatenablog

いわゆるチラシノウラであります

Mail.Ru Cup 2018 Round 3 B. Divide Candies

出てないけど

http://codeforces.com/contest/1056/problem/B
なおや氏なら2分でできると思うが、良問だったように思う
(なおや氏なら2分で出来る、としておくとブログが生えることに気づいたw)

こういう唆し方をしてくる御仁がいるので解いてみた(2分よりはかかった)メモ。

$$ n^2\mod{}m = (n\mod{}m)^2\mod{}m $$ なので
$$ (i^2+j^2)\mod{}m = ((i\mod{}m)^2 + (j\mod{}m)^2)\mod{}m $$
1\le i,j\le mについて、i^2をmで割った余りの数が何回ずつ出てくるかを集計して(余り、というかn%mについては+1ずつして)、足してm(というか0 mod m)になるようにしたいので先程の集計の数を(m-k)%mに差し替えたやつを作って、あとはO(m^2)の掛け算で
そしてlong longじゃないと駄目だよなこれ、と思って書き換えた

intで書いてたやつを投げちゃって
→WA(1)
https://codeforces.com/contest/1056/submission/46234354

long longのやつを提出して
→AC
https://codeforces.com/contest/1056/submission/46234369

typedef long long ll;
typedef vector<ll> vll;
#define rep(var,n)  for(int var=0;var<(n);++var)
ll solve(int n, int m) {
    ll a = n/m, b = n%m;
    vll r(m); rep(i,m) r[i] = (i+1)*(i+1)%m;
    vll st(m, 0); rep(i,m) st[r[i]] += a;
    rep(i,b) st[r[i]]++;
    vll st_(m, 0); rep(i,m) st_[i] = st[(m-i)%m];
    ll ans = 0;
    rep(i,m) ans += st[i] * st_[i];
    return ans;
}