[java]
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);
}
}
}
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的铁丝，将其分成有顺序的若干份，每份折成三角形，要求所有的三角形相似，
HDU4466 Triangle
，电脑资料
《HDU4466 Triangle》(https://www.unjs.com)。三角形顺序不同视为不同方案，三边相等视为同一方案。求方案个数。
首先定义f(x)表示周长为x的三角形个数。
我们用(a,b,c)表示一个三角形，其中a <= b <= c
将f(x)的所有三角形分为两部分，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全部预处理出来