Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-11-06

SRM 367 Div1 Easy ObtainingDigitK

18:25 | SRM 367 Div1 Easy ObtainingDigitK - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 367 Div1 Easy ObtainingDigitK - chokudaiの日記 SRM 367 Div1 Easy ObtainingDigitK - chokudaiの日記 のブックマークコメント

問題

文字列型ででっかい数字が与えられる いくつ足せば0-9までの整数kが出てくるか求めなさい

originalNumberは50文字までの10進文字列

方針

BigIntegerあれば困らないなぁと思いつつ、BigIntegerもどきを自力実装

もうちょっと手抜ける気もしたけどこれで余裕だからいいやw

ソースコード

ひどいけど・・・w

    public int minNumberToAdd(string originalNumber, int k)
    {
        int[] digit = new int[101];
        int i,j;
        for (i = 0; i < originalNumber.Length; i++) digit[originalNumber.Length - i - 1] = originalNumber[i] - '0';
        for (i = 0; i < 10; i++)
        {
            for (j = 0; j < originalNumber.Length + 1; j++)
            {
                if (j == originalNumber.Length && digit[originalNumber.Length] == 0) continue;
                if (digit[j] >= 10) { digit[j + 1]++; digit[j] -= 10; }
                if (digit[j] == k) return i;
            }
            digit[0]++;
        }
        return 9;
    }

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余る約数の数

 |