結果
問題 | No.2249 GCDistance |
ユーザー |
|
提出日時 | 2023-03-17 21:41:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,555 ms / 5,000 ms |
コード長 | 2,417 bytes |
コンパイル時間 | 1,776 ms |
コンパイル使用メモリ | 138,000 KB |
最終ジャッジ日時 | 2025-02-11 12:45:52 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
//pypyの遅さをなめるなよ()#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <iostream>#include <vector>#include <string>#include <map>#include <set>#include <queue>#include <algorithm>#include <cmath>#include <iomanip>#include <random>#include <stdio.h>#include <fstream>#include <functional>#include <cassert>using namespace std;#define rep(i,n) for (int i=0;i<n;i+=1)#define append push_back#define all(x) (x).begin(), (x).end()template<class T>using vec = vector<T>;template<class T>using vvec = vec<vec<T>>;template<class T>using vvvec = vec<vvec<T>>;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;template<class T>bool chmin(T &a, T b){if (a>b){a = b;return true;}return false;}template<class T>bool chmax(T &a, T b){if (a<b){a = b;return true;}return false;}template<class T>T sum(vec<T> x){T res=0;for (auto e:x){res += e;}return res;}template<class T>void printv(vec<T> x){for (auto e:x){cout<<e<<" ";}cout<<"\n";}template<class T>ostream& operator<<(ostream& os, const vec<T>& A){os << "[";rep(i,A.size()){os << A[i];if (i!=A.size()-1){os << ", ";}}os << "]" ;return os;}template<class T>ostream& operator<<(ostream& os, const deque<T>& A){os << "deque{[";rep(i,A.size()){os << A[i];if (i!=A.size()-1){os << ", ";}}os << "]}" ;return os;}template<class T>ostream& operator<<(ostream& os, const pair<T,T>& A){os << "(";os << A.first ;os << ", ";os << A.second;os << ")";return os;}const ll M = 10000000;ll mebius[M+1],phi[M+1];void calc(){mebius[0] = 0;for (ll n=0;n<=M;n++){mebius[n] = 1ll, phi[n] = (ll)n;}for (ll p=2;p<=M;p++){if (phi[p]==p){for (ll k=p;k<=M;k+=p){mebius[k] *= -1ll;if (k%(p*p) == 0ll){mebius[k] = 0ll;}}}if (mebius[p]!=0ll){for (ll k=p;k<=M;k+=p){phi[k] += mebius[p] * (ll)(k/p);}}}for (int n=1;n<=M;n++){phi[n] += phi[n-1];}}int main() {ios::sync_with_stdio(false);std::cin.tie(nullptr);calc();int T;cin>>T;while (T--){ll N;cin>>N;ll res = N*(N-1) - (phi[N]-1);cout << res << endl;}}