HDU4466 Triangle

import java.util.Scanner;



public class Main {

	static Scanner cin = new Scanner(System.in);

	static int N = 5000000, m = 1000000007;

	static int n, f[] = new int[N + 10], p2[] = new int[N + 10], C;



	private static void init() {

		f[3] = 1;

		p2[1] = 1;

		p2[2] = 2;

		for (int i = 4; i <= N; i++) {

			f[i] = f[i - 1] + (i - 1) / 2 - i / 3 + (i % 3 != 0 ? 0 : 1);

			if ((i & 1) == 0)

				f[i] -= i / 4;

			if (f[i] >= m)

				f[i] -= m;

			if (f[i] < 0)

				f[i] += m;

		}

		for (int i = 3; i <= N; i++) {

			p2[i] = p2[i - 1] << 1;

			if (p2[i] >= m)

				p2[i] -= m;

			for (int j = i + i; j <= N; j += i) {

				f[j] -= f[i];

				if (f[j] < 0)

					f[j] += m;

			}

		}

	}



	public static void main(String[] args) {

		init();

		while (cin.hasNext()) {

			n = cin.nextInt();

			long ans = 0;

			for (int i = 1; i * i <= n; i++)

				if (n % i == 0) {

					ans = (ans + (long) f[i] * p2[n / i]) % m;

					if (i * i != n)

						ans = (ans + (long) f[n / i] * p2[i]) % m;

				}

			System.out.println("Case " + ++C + ": " + (ans + m) % m);

		}

	}



}

タイトル:
長さnの針金を与え、順序のあるいくつかの部に分け、各部を三角形に折り、すべての三角形が似ていることが要求される.
三角形の順序が異なる場合は異なるスキームとみなされ、3辺が等しい場合は同じスキームとみなされます.シナリオの個数を求める.
 
まずf(x)を定義して周長xの三角形の個数を表す.
(a,b,c)を用いて三角形を表し,ここでa<=b<=c
f(x)のすべての三角形を2つの部分に分けて、b=cとb!=cの
b=cの三角形の個数
aは少なくとも1であり、cの最大値はfloor((x-1)/2)である.
a<=b<=cであるため、cの最小値はceil(x/3)である
個数はfloor((x−1)/2)−ceil(x/3)+1である.注意xが小さい場合は、最大値が最小値より小さい場合がありますが、この場合差は-1、プラス1で0となり、結果に影響しません.
簡略化後はプログラム中の(i-1)/2-i/3+(i%3?0:1)
b!=cの三角形の個数
b!=c,bそしてa+b>c>c-1
したがって,(a,b,c−1)も必ず三角形である.
したがって、この部分のスキーム数は、f(x−1)からf(x−1)を減算するa+b=c+1を満たす三角形に等しい.
a+b=c+1を含む三角形のxは必ず奇数である.
このときc=(x-1)/2
シナリオ数floor((x-(x-1)/2)/2)
簡略化後はプログラム中の(x+1)/4
次にg(x)を周長xの本質的な三角形個数と定義する(公式現場問題解が与える概念は,三辺最大公約数が1の三角形である)
g(x)=f(x)−sigma(g(k))は、kがxのすべてのxよりも小さい約数であり、nlognがすべて前処理できる