Peking University Online Judge 2409 Let It Bead
昨日のコードを少しだけ弄ってAC
#include<cstdio> #include<vector> using namespace std; typedef long long int ll; static const int MAX_CS = 32; int c, s; vector<ll> va[MAX_CS + 1]; int gcd(int a, int b){ if(b == 0) return a; else return gcd(b, a % b); } int main(){ for(int i = 1; i <= MAX_CS; i++){ for(int j = 0; j * i <= MAX_CS; j++){ if(j == 0) va[i].push_back(1LL); else va[i].push_back(va[i].back() * (ll)i); } } for(;;){ scanf("%d %d", &c, &s); if(c == 0 && s == 0) break; ll res = 0; for(int i = 1; i <= s; i++){ if(i == 1 || i == s){ res += va[c][s / i]; }else if(gcd(s, i) != 1){ res += va[c][gcd(s, i)]; }else{ res += c; } } for(int i = 1; i <= s; i++){ if(s % 2 == 0){ if(i % 2 == 0){ res += va[c][s / 2]; }else{ res += va[c][(s - 2) / 2 + 2]; } }else{ res += va[c][(s - 1) / 2 + 1]; } } printf("%lld\n", res / (ll)(s * 2)); } return 0; }