B. Divide Candies (思維)

題目連結：B. Divide Candies

題意：

給兩個整數n，m，問有多少種情況滿足(i2 + j2) % m == 0 (1 <= i, j <= n);

題解：

我們将式子轉化一下，變可以得到如下結果

(i2 + j2) % m = (i2 %m+ j2%m) %m = ((i % m * i % m) + (j % m * j % m)) % m

如此我們就隻需要統計餘數0~m-1有多少個即可，用cnt數組存儲個數

然後枚舉餘數i，j，計算答案

int cnt[N];
int main()
{
    int n, m; scanf("%d%d", &n, &m);
    //統計餘數的個數
    for (int i = 0; i < m; i ++ ) cnt[i] = n / m;
	//對餘下的數單獨統計
    for (int i = n; i > n - n % m; i -- ) cnt[i % m] ++;
    LL ans = 0;
    //枚舉餘數
    for (int i = 0; i < m; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            if ((i * i + j * j) % m == 0)
                ans += 1ll * cnt[i] * cnt[j];
        }
    }
    printf("%lld\n", ans);
    return 0;
}