Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-11-06

SRM 365 Div1 Easy PointsOnCircle

17:45 | SRM 365 Div1 Easy PointsOnCircle - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 365 Div1 Easy PointsOnCircle - chokudaiの日記 SRM 365 Div1 Easy PointsOnCircle - chokudaiの日記 のブックマークコメント

問題

中心が格子点上にある半径rの円が与えられる。格子点を通っている数を求めよ。 r<2*10^9

公式として、個数=4**1ガ与えられる

方針

Easyにしてはむずかしめ

  1. rに関してi=2からループしてrで割りまくる i*i>rになったらiをrまで飛ばしておk
  2. 実際に必要なのはr*rの約数だから、実際の個数の2倍あることに注意して適当に、今持ってる約数を4で割った余りごとにdp
  3. 最後は公式どおり計算するだけ

ソースコード

public class PointsOnCircle
{
    public long count(int r)
    {
        long i,j;
        int k;
        long[] dp = new long[4];
        dp[1] = 1;
        for (i = 2; i <= r; i++)
        {
            if (i * i > r) i = r;
            long[] adddp = new long[4];
            for (j = i; r % i == 0; j *= i * i)
            {
                r /= (int)i;
                for (k = 0; k < 4; k++) adddp[(k * j) % 4] += dp[k];
                for (k = 0; k < 4; k++) adddp[(k * j % 4 * i) % 4] += dp[k];
            }
            for (k = 0; k < 4; k++) dp[k] += adddp[k];
        }
        Console.WriteLine(dp[1] + " " + dp[3]);
        return 4 * (dp[1] - dp[3]);
    }
}

*1:r*rの4で割ると1余る約数の数)-(r*rの4で割ると3余る約数の数

 |