結果
問題 | No.1514 Squared Matching |
ユーザー | yakki |
提出日時 | 2021-05-22 00:34:28 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,251 ms / 4,000 ms |
コード長 | 1,406 bytes |
コンパイル時間 | 1,523 ms |
コンパイル使用メモリ | 122,576 KB |
実行使用メモリ | 400,136 KB |
最終ジャッジ日時 | 2024-04-18 17:10:25 |
合計ジャッジ時間 | 38,900 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2,251 ms
400,068 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 30 ms
9,328 KB |
testcase_07 | AC | 393 ms
79,024 KB |
testcase_08 | AC | 2,068 ms
385,664 KB |
testcase_09 | AC | 1,787 ms
337,428 KB |
testcase_10 | AC | 1,988 ms
365,312 KB |
testcase_11 | AC | 2,042 ms
380,544 KB |
testcase_12 | AC | 2,117 ms
390,908 KB |
testcase_13 | AC | 2,137 ms
396,124 KB |
testcase_14 | AC | 2,158 ms
398,280 KB |
testcase_15 | AC | 2,177 ms
399,244 KB |
testcase_16 | AC | 2,151 ms
399,616 KB |
testcase_17 | AC | 2,153 ms
400,000 KB |
testcase_18 | AC | 2,163 ms
399,888 KB |
testcase_19 | AC | 2,163 ms
400,136 KB |
testcase_20 | AC | 2,165 ms
399,944 KB |
testcase_21 | AC | 2,167 ms
399,908 KB |
testcase_22 | AC | 411 ms
82,660 KB |
testcase_23 | AC | 825 ms
162,048 KB |
testcase_24 | AC | 1,247 ms
241,280 KB |
testcase_25 | AC | 1,715 ms
320,560 KB |
ソースコード
#include<iostream> #include<string> #include<vector> #include<algorithm> #include<bitset> #include<set> #include<map> #include<stack> #include<queue> #include<deque> #include<list> #include<iomanip> #include<cmath> #include<cstring> #include<functional> #include<cstdio> #include<cstdlib> #include<numeric> //#include<atcoder/all> using namespace std; //using namespace atcoder; #define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rep(i, n) repr(i, 0, n) #define INF 2e9 #define MOD 1000000007 //#define MOD 998244353 #define LINF (long long)4e18 #define jck 3.141592 #define PI acos(-1.0) const double EPS = 1e-10; using ll = long long; using Pi = pair<int,int>; using Pl = pair<ll,ll>; ll square_sum(int a){ return (ll)sqrt(a); } int main(){ int n; cin >> n; ll ans = 0; vector<ll> to_prod(n+1); vector<bool> prime(n+1,true); for(ll i = 2; i*i <= n; i++){ if(!prime[i]) continue; for(int j = i+i; j <= n; j+=i){ prime[j] = false; } } repr(i,1,n+1) to_prod[i] = i; for(ll i = 2; i*i <= n; i++){ if(prime[i]){ ll k = i*i; for(ll j = k; j <= n; j+=k){ while(to_prod[j]%k==0) to_prod[j] /= k; } } } repr(i,1,n+1){ if(to_prod[i] <= n){ ans += square_sum(n/to_prod[i]); } } cout << ans << endl; }