結果

問題 No.2979 直角三角形の個数
コンテスト
ユーザー 2qbingxuan
提出日時 2024-12-24 01:34:33
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,638 bytes
コンパイル時間 3,005 ms
コンパイル使用メモリ 248,772 KB
実行使用メモリ 65,828 KB
最終ジャッジ日時 2024-12-24 01:35:09
合計ジャッジ時間 32,280 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 24 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef local
#define safe cerr << __LINE__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int cnt = sizeof...(T);
  (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
  cerr << "\e[1;32m[ " << s << " ] = [ ";
  for (int f = 0; L != R; ++L)
    cerr << (f++ ? ", " : "") << *L;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using lld = int64_t;

const int maxn = 1000025;
vector<int> prime_factor[maxn];

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  // m^2+n^2, m^2-n^2, 2mn, gcd(m, n) == 1, parity of m, n are different
  // perimeter = g * (2m^2+2mn) <= N -> n <= (N/2mg) - m

  for (int i = 2; i < maxn; i++) {
    if (prime_factor[i].empty()) {
      for (int j = i; j < maxn; j += i)
        prime_factor[j].push_back(i);
    }
  }

  long double total_time = 0;
  lld N;
  cin >> N;
  lld ans = 0;
  for (int m = 2; 1LL * 2 * m * m <= N; m++) {
    auto calc = [&](lld lim) -> lld {
      if (lim < 0) return 0;
      if (lim >= m) lim = m - 1;
      lld sum = 0;
      auto dfs = [&](auto &&self, size_t i, lld x, int coef) {
        if (i == prime_factor[m].size()) {
          if (m & 1) {
            sum += coef * (x / 2);
          } else {
            sum += coef * x;
          }
          return;
        }
        self(self, i + 1, x, coef);
        self(self, i + 1, x / prime_factor[m][i], -coef);
      };
      dfs(dfs, 0, lim, 1);
      return sum;
    };

    // g <= (N / 2m) / (m + n)
    lld L = N / (2 * m);
    // total_time += sqrt(L); // * (1 << prime_factor[m].size());
    lld last = 0;
    for (lld i = m, j; i <= L && i <= 2 * m; i = j) {
      lld q = L / i;
      j = L / q + 1;
      // if (m + n) \in [i, j) then L / (m + n) == q

      /*
      for (lld n = i - m; n < j - m; n++)
        if (n > 0 && n < m && gcd(m, n) == 1 && ((m ^ n) & 1))
          ans += q;
      */
      lld cur = calc(j - m - 1);
      ans += q * (cur - last);
      last = cur;
    }
    /*
    for (int g = 1; m * m * g <= N; g++) {
      lld bound = min<lld>(m - 1, N / (2 * m * g) - m);
      debug(bound);
      for (int n = 1; n <= bound; n++)
        if (gcd(n, m) == 1 && ((m ^ n) & 1)) {
          // debug(m*m + n*n, m*m - n*n, 2*m*n);
          ++ans;
        }
    }
    */
  }
  debug(total_time);

  cout << ans << '\n';
}
0