>>566の続き 最深のループは実は回す必要がない その前のレベルまでの総計とnとの差が最深のループの硬貨の単価で割り切れる場合だけカウントすればいい for (int a = 0; a <= n; a += 1) { for (int b = a; b <= n; b += 5) { for (int c = b; c <= n; c += 10) { if ((n - c) % 20 == 0) count++; さらに硬貨の種類に1円が存在する特別な場合はループの順番を入れ替えれば剰余計算が必要なくなる for (int a = 0; a <= n; a += 20) { for (int b = a; b <= n; b += 10) { for (int c = b; c <= n; c += 5) count++; そしてこの3段目のループは単にb,b+5,b+10,...<=nの個数をcountに加えているだけなのでこれも回す必要はない よって public class Hoge { public static void main(String[] args) { System.out.println(A(10000)); } public static long A(int n) { long count = 0; for (int a = 0; a <= n; a += 20) { for (int b = a; b <= n; b += 10) { count += (n - b) / 5 + 1; } } return count; } } この調子でループを内側からどんどん潰して最終的にカウントなしにできると思うけれど 導出が面倒だし見た目も悪いものになるんじゃないかと思うのでこの程度で打ち切り このくらいでもマシン次第ではあるがA(10000)程度なら時間はほとんどかからないと思う うちのPCで計るとA(100000)でも1秒かからなかった 正答を知らないから正しくカウントしているかどうかは分からない
