[Codeforces][Round #736][Div.2] A : Gregor and Cryptography

https://codeforces.com/contest/1549/problem/A

Problem - A - Codeforces

 

[난이도] Div.2
[유형] 수학

[풀이]
P가 소수일 때, P mod a=P mod b 를 만족하는 a,b를 찾는 문제입니다.
P가 소수이면 P-1은 반드시 1이외의 약수가 존재할 것이라는 생각으로
P-1의 약수를 찾는 O(루트N) 알고리즘을 적용하여
P-1의 약수중 가장 작은 수와 P-1을 출력해서 AC를 받았습니다.

컨테스트 종료 후 튜토리얼을 보니 P-1은 당연히 짝수이니 2와 P-1을 출력해주면 되는
훨씬 간단한 문제였습니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <map>
using namespace std;
using ll = long long;

int tc,P;

int sol(int p){

    for(int i=2;i<=sqrt(p);i++){
        if(p%i==0){
            return i;
        }
    }
    return 0;
}

int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&P);
        printf("%d %d\n",sol(P-1),P-1);
    }

}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round736-Div.2/A.cpp