https://www.acmicpc.net/problem/13412


입력 받은 N의 쌍을 먼저 만듭니다.


ex) N = 30 이라면.. (1, 30) ... (30, 1) 까지의 쌍이 있겠죠

하지만 (1, 30) (30, 1)은 같은 쌍이고, (2, 15), (15, 2)는 같은 쌍입니다.


그렇기 때문에 sqrt(N)까지만 쌍을 만들면 해결할 수 있습니다.


여기서 주의할 것은 약수라고 무조건 카운트하면 안됩니다.

두 쌍의 최대공약수가 1인 즉 서로소일 경우에만 쌍을 카운트해야 합니다.


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
45
46
47
48
49
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
#include <cstdio>
 
#define mp make_pair
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int get_gcd(int a, int b) {
    return b ? get_gcd(b, a % b) : a;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int test;
    cin >> test;
 
    while (test--) {
        int n;
        cin >> n;
 
        int ret = 0;
 
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0 && get_gcd(i, n / i) == 1) {
                ret++;
            }
        }
 
        cout << ret << '\n';
    }
    return 0;
}
cs


저작자표시

'알고리즘 > 수학' 카테고리의 다른 글

[2436] 공약수  (2) 2017.09.01
[1740] 거듭 제곱  (0) 2017.06.21

https://www.acmicpc.net/problem/2436


문제에서 인풋으로 GCD와 LCM을 줍니다.

우리는 그렇다면

어떤 수 a, b가 있다고 존재할 때

A = a / GCD

B = b / GCD

라고 한다면


LCM = GCD * A * B

라는 것을 알 수 있습니다.


여기서 가장 중요한 조건 ! A와 B는 서로소여야만 한다는 것입니다.

서로소라는 것은 두 수는 약수를 1만을 가진다는 것인데요.


이 조건을 만족하지 않으면 A와 B는 후보가 될 수 없습니다.

예륻 들어 GCD가 4라는 인풋이 들어왔는데 A가 2 B가 4라면

더 나눌 수 있는 수가 존재하므로 후보가 아니라는 말이죠.


그 외에는 어려운 부분은 없었습니다.

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
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int get_gcd(int a, int b) {
    return b ? get_gcd(b, a % b) : a;
}
 
int main() {
    int gcd, lcm;
    cin >> gcd >> lcm;
 
    int tmp = lcm / gcd;
 
    int left = 0, right = 0;
 
    for (int i = 1; i * i <= tmp; i++) {
        if (tmp % i == 0) {
            if (get_gcd(i, tmp / i) == 1) {
                left = i;
                right = tmp / i;
            }
        }
    }
 
    if (left > right) swap(left, right);
 
    cout << left * gcd << ' ' << right * gcd;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 수학' 카테고리의 다른 글

[13412] 서로소 쌍  (0) 2017.09.07
[1740] 거듭 제곱  (0) 2017.06.21

https://www.acmicpc.net/problem/1740


와 너무 신기한 문제에요..ㅠㅠ

N이 진짜 말도안되게 커서 어떻게 접근해야할지 감도 안왔습니다..


규칙이 있나 찾아봤는데 규칙이 있는 것도 아니였습니다.


자료를 찾다보니... 3의 제곱수를 하나씩만 사용할 수 있는게 힌트였습니다!


진짜 엄청난 힌트더군요..


자꾸 사람들이 2진수 이야기를 하길래 무슨 소린가...했는데..


3의 제곱수를 하나씩만 사용한다는 얘기는 !!!

27 9 3 1 이렇게 있다고 치면!

                

27

9

3

1

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

0

0

0

1

0

0

1


어디서 많이 보던!!!!!! 표입니다!

그렇습니다! 하나만 쓰게되면 이진수처럼 됩니당!

그래서 N을 2진수로 바꾼 후에 이 2진수를 3진수를 이용해서 10진수로 바꾸면! 결과가 나옵니다.


예제에 N = 4였습니다.

4는 2진수로

100 입니다! 3진수로 100은 9입니다.

그래서 답은 9죠!


진짜 재밌는 문제입니다..... 소오름~~~

아래는 코드입니다.

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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
 
#define ll long long
using namespace std;
 
int main() {
    ll n;
    scanf("%lld", &n);
    
    queue<bool> q;
    while (n) {
        q.push(n % 2);
        n /= 2;
    }
 
    ll ans = 0;
    ll add = 1;
 
    while (!q.empty()) {
        ans += q.front() * add;
        add *= 3;
        q.pop();
    }
 
    printf("%lld", ans);
    
    return 0;
}
 
cs


'알고리즘 > 수학' 카테고리의 다른 글

[13412] 서로소 쌍  (0) 2017.09.07
[2436] 공약수  (2) 2017.09.01

+ Recent posts

티스토리툴바