1511-B, *1100

Problem - 1511B - Codeforces

문제

• $\mathrm{gcd(a,\ b)}$가 $c$ 자리수이고 각각의 자리수가 $a,\ b(1\leq a,\ b \leq 9)$인 두 수 A, B를 구하라

 

$O(1)$

$c$ 자리의 소수를 $\mathrm{gcd(A,\ B)}$라고 두고 A 와 B 를 만든다
$\mathrm{(A,\ B)}$가 변하면 안되므로 $\mathrm{(A,\ B)}$에 서로다른 소수를 곱하여 A 와 B 를 만든다

Claim
각각의 자리수가 $a,\ b(1\leq a,\ b \leq 9)$인 두 수 A, B 에 대해
두 수의 최고자리수가 모두 3 이하면 AB는 a+b-1 자리수이다

$\because$
AB의 자릿수는 A와 B의 최고자릿수의 곱만 보면 된다
Let
A $\rightarrow {a}'\cdot10^{a-1}$,
B $\rightarrow {b}'\cdot10^{b-1}$

AB $\rightarrow {a}'{b}'\cdot10^{a+b-2}$, ${a}'{b}'\leq 9$
따라서 AB는 a+b-1 자리수이다□

이제 최고자리수가 3 이하인, 1~9 자리의 소수를 구하자

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int find;
 
bool isprime(int p, int& find)
{
    bool flag = true;
    for(int i = 3; i*i <= p; i+=2){
        if(p%i == 0) flag = false;
    }
    if(flag){
        cout << p << endl;
        find++;
        return true;
    }
    else return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int p;
    for(int i = 1; i <= 8; i++){
        p = pow(10, i)+1;
        int find = 0;
        while(!isprime(p, find) or find < 2) {
            p += 2;
        }
    }
 
 
    return 0;
}cs

11 13 101 103 1009 1013 10007 10009 100003 100019 1000003 1000033 10000019 10000079 100000007 100000037 Process finished with exit code 0

이를 이용해서 코드를 구성하면 된다

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int a, b, c;
map<int, vector<int> > m = {
        {0, {2, 3}},
        {1, {11, 13}},
        {2, {101, 103}},
        {3, {1009, 1013}},
        {4, {10007, 10009}},
        {5, {100003, 100019}},
        {6, {1000003, 1000033}},
        {7, {10000019, 10000079}},
        {8, {100000007, 100000037}}
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> a >> b >> c;
        cout << m[c-1][0]*m[a-c][0] << ' ' << m[c-1][0]*m[b-c][1] << endl;
    }
 
    return 0;
}cs

$O(1)$

$111\cdot \cdot \cdot 111$와 $100\cdot \cdot \cdot 000$은 서로소임을 이용한다

$$\begin{align*} &gcd(A,\ B)=10^{c-1}\\ &\text{A}=1\underset{a-c}{\underbrace{00..00}}\underset{c-1}{\underbrace{00..00}}\\ &\text{B}=1\underset{b-c}{\underbrace{11..11}}\underset{c-1}{\underbrace{00..00}} \end{align*}$$

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int a, b, c;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> a >> b >> c;
        cout << 1;
        loop(i, a-1) cout << 0;
        cout << ' ';
        loop(i, b-c+1) cout << 1;
        loop(i, c-1) cout << 0;
        cout << endl;
    }
 
    return 0;
}cs