Submission #00084

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
map< int64_t, int > prime_factor(int64_t n) {
map< int64_t, int > ret;
for(int64_t i = 2; i * i <= n; i++) {
while(n % i == 0) {
ret[i]++;
n /= i;
}
}
if(n != 1) ret[n] = 1;
return ret;
}
signed main(){
int m;
cin >> m;
auto mp = prime_factor(m);
int ans = m;
vector<int> so;
for(auto e : mp){
so.push_back(e.first);
}
for(int i = 1;i < (1 << so.size());i++){
int b = __builtin_popcount(i);
int x = 1;
for(int j = 0;j < so.size();j++){
if(i & (1 << j)) x *= so[j];
}
ans += (b % 2 == 1 ? -1 : 1) * (m / x);
}
cout << ans << endl;
return 0;
}

ステータス

項目 データ
問題 0008 - ヒトⅢ
ユーザー名 ei1719
投稿日時 2020-04-25 22:04:17
言語 C++14
状態 Accepted
得点 400
ソースコード長 896 Byte
最大実行時間 28 ms
最大メモリ使用量 668 KB

セット

セット 得点 Cases
1 ALL 400 / 400 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 23 ms 604 KB
1
in02.txt AC 20 ms 572 KB
1
in03.txt AC 22 ms 668 KB
1
in04.txt AC 21 ms 508 KB
1
in05.txt AC 21 ms 484 KB
1
in06.txt AC 17 ms 452 KB
1
in07.txt AC 15 ms 428 KB
1
in08.txt AC 23 ms 528 KB
1
in09.txt AC 17 ms 628 KB
1
in10.txt AC 16 ms 476 KB
1
in11.txt AC 27 ms 580 KB
1
in12.txt AC 28 ms 556 KB
1
in13.txt AC 26 ms 404 KB
1
in14.txt AC 21 ms 508 KB
1
in15.txt AC 17 ms 484 KB
1
in16.txt AC 17 ms 588 KB
1
in17.txt AC 23 ms 560 KB
1
in18.txt AC 19 ms 532 KB
1
sample01.txt AC 25 ms 624 KB
1
sample02.txt AC 28 ms 600 KB
1
sample03.txt AC 21 ms 572 KB
1