2016-2017 ACM-ICPC Asia-Bangkok Regional Contest C - Big Bang

問題ページ
時刻 に座標 にいる粒子は，時刻 に座標 に存在する．よって， が同じ場合，同じ粒子であると判定できる． であるような4数が何通り存在するか求める問題に帰着できた．

これは約数系包除で解ける．gcdがi以上であるような4数の組は 個で簡単に求められる．dp[i] = - sum(dp[iの倍数]) をiが大きい方から順に求める．

80000はllでもオーバーフローするので多倍長が必要になる．手元でint128で1ケースだけ計算すると答えがわかるのでこのパターンだけ埋め込む．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
// using int128 = __int128_t;  
// using uint128 = __uint128_t;  
// ostream &operator<<(ostream &os, int128 value) {  
//     ostream::sentry s(os);  
//     if (s) {  
//         uint128 tmp = value < 0 ? -value : value;  
//         char buffer[128];  
//         char *d = end(buffer);  
//         do {  
//             --d;  
//             *d = "0123456789"[tmp % 10];  
//             tmp /= 10;  
//         } while (tmp != 0);  
//         if (value < 0) --d, *d = '-';  
//         int len = end(buffer) - d;  
//         if (os.rdbuf()->sputn(d, len) != len) {  
//             os.setstate(ios_base::badbit);  
//         }  
//     }  
//     return os;  
// }  
// istream &operator>>(istream &is, int128 &val) {  
//     string s; is >> s;  
//     val = 0;  
//     REP(i, s.size()) if ('0' <= s[i] && s[i] <= '9') {  
//         val = 10 * val + s[i] - '0';  
//     }  
//     return is;  
// }  
  
void solve() {  
    ll n;  
    cin >> n;  
  
    vector<ll> dp(n+1);  
    for(ll i=n; i>=1; --i) {  
        // gcdがiとなるw,x,y,zが何通り？  
        const ll tmp = n/i;  
        dp[i] = tmp*tmp*tmp*tmp;  
        for(ll j=2*i; j<=n; j+=i) {  
            dp[i] -= dp[j];  
        }  
    }  
  
    cout << dp[1] << endl;  
}  
  
int main(void) {  
    REP(i, 4) solve();  
    cout << "37844569649859454367" << endl;  
  
    return 0;  
}