CodeIQの実力判定Aランク問題でタイムアウトしてしまう。

Question

CodeIQの問題をやっていたのですがタイムアウトしてしまいます。

###問題

問題は以下です。

【問題】
1から1,000,000までの整数の範囲で、連続する2値を合計します。
2値の合計が、整数Nの倍数になる組み合わせを、数えてください。
ただし、整数Nは、2≦N≦1,000 の範囲とします。

例
整数Nが11の場合、「5, 6（合計は11）」、「16,17（合計は33）」……という組み合わせが、整数Nの倍数になります。
また、連続する2値の最小は「1, 2（合計は3）」、最大は、「999999, 1000000（合計は1999999）」になります。

【入力】
標準入力から、複数行のデータが与えられます。1行のデータが、1つの整数Nになります。

【出力】
1行ずつ処理を行ない、その答えを1行ごと標準出力に出力します。

【入出力サンプル】
Input
307
456
545
165

Output
3257
0
1835
6061

ログインが必要なため、以下より転載
https://codeiq.jp/challenge/3117

###作成したコード

using System;

public class hoge
{
	static void Main()
	{
		string line;
		int num, count = 0, val = 0;

		for(;(line=Console.ReadLine()) != null;)
		{
			if(int.TryParse(line, out num))
			{
				for(int i=1;i<1000000;i++)
				{
					val = i + (i+1);
					val %= num;
					if(val == 0)
						count++;
				}
				Console.WriteLine(count);
			}
		}
	}
}

for分で回すのがいけないのかなと思いましたが最適解がよくわかりません。
ヒントの様なものでも構いませんので何か教えてください。。。

###追記
処理制限時間は1秒です。

Answer 1

CodeIQ運営事務局からのお願いと連絡事項
解答送信の有無を問わず、模範解答のネタばれにつながるような各種行為、別人による不正解答は、固くお断り申し上げます。

CodeIQ運営事務局 スキルチェック部さんからの問題より。

との注意があるので、ふんわりとした回答のみにとどめます。

• 連続する２値にはある縛りがあります。
• とりあえず最小の組み合わせを探します。

Comments

[maisumakun]

他人から聞けるのも「実力」のうち、かもしれませんが、おおっぴらにやるのは良くないですよね。

[退会済みユーザー]

その様な規約が。。。
ご指摘ありがとうございます。

[8524ba23]

ですね。あと自力でとことん考えたうえで解けたときの快感もあるので。

[8524ba23]

>tottyさん
いえいえ^-^

Answer 2

連続する2つの値ですから、x + (x+1) が N の倍数ですよね。
つまり 2x+1 が N になる値を一つ見つけることができれば、あとは 1000000 までに何回加算できたか分かればよいのでは。

で、2x+1 が N になるということは、変形して 2x = N-1 ですから、x = (N-1)/2 ですよね。
でもって、次の N の倍数を構成する2値のうち小さい方をy とすると、すなわち 2y+1 = 2N ですから、 2y = 2N-1 = N + N-1 より、y = (N/2) + (N-1)/2 です。つまり、y = x + (N/2) になります。
なので、最初の x さえ分かれば、あとは N/2 を足していき、 x<1000000 になるまでの加算回数をカウントするだけでいいのでは。

Comments

[退会済みユーザー]

単純な数学の問題のような感じですかね。
数学とか最近まったくなので問題文通りにしかコードをかけていませんでした。。。

ちょっと試してみます。

[tacsheaven]

ちょこちょこ修正しましたが、上のことから、x は計算ですぐ求まります。でもって N/2
（切り捨て） も計算ですぐ分かりますから、(1000000-x)/(N/2) で、何回加算可能かも（実際にループさせなくても）分かりますね。
でもって条件から、最初の N が偶数の場合は 0 に固定されます（Nは奇数でないとそもそも該当する2値が存在しえません）、と。

[tacsheaven]

CodeIQ の場合、こういう「問題から規則性・法則性を見つけ出して えれがんと な解法を書く」問題が多いように思います（ｗ