SCCC - Soongsil Computing Contest Club/2020 Winter-Study
4. 정수론-소인수분해, gcd, lcm, sieve
Mosu(정종인)
2020. 1. 14. 02:51
반응형
4.md
0.01MB
- 복습
- mod n
- 덧셈
7 = 3 (mod 4)
ex) a+b = (a+b)%n (mod n)
7 + 9 = 16 = 0 (mod 4)
3 + 1 = 4 = 0 (mod 4)
12312312 + 234234234 = 0 + 2 = 2 (mod 4)
- 곱셈
7*9 = 63 = 3 (mod 4)
3 * 1 = 3 (mod 4)
즉, 미리 mod를 적용해주면 식이 간단해진다.
답이 심각하게 커지는 경우, mod를 많이 쓰며 나중에 다이나믹 프로그래밍에서 많이 나온다.
참고 문제 : [boj.kr/17466]
- 소인수 분해
어떤 수를 소인수 분해 하려면, 2부터 sqrt(N)까지 원소들의 조건을 따지면서 분해하면 된다.
(1) N이 합성수인 경우, N = p1^r1 * p2^r2 * p3^r3 * ... * pk^rk
N = 2^r1 * 3^r2 * 5^r3 * p4^r4
- 어떤 N이 오직 sqrt(N)보다 작은 소인수로 이루어짐
이때는 자명하므로 패스.
- 어떤 N을 소인수 분해했을 때 sqrt(N)보다 큰 소인수도 있음
sqrt(N)보다 큰 소인수는 지수가 무조건 1이다. (하나밖에 없다) => 지수가 2개 이상이면 그 2개만으로 N을 넘어버리기 때문에 1개밖에 없다.
(2) N이 소수인 경우, 어떤 N을 소인수 분해했을 때 sqrt(N)보다 큰 소인수도 있다는 조건과 같음. 따라서 예외처리할 필요 없음.
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int> > v;
int main(){
int N; cin >> N;
for(int p=2; p*p<=N; ++p){
int cnt=0;
while(N%p==0){
N/=p;
cnt++;
}
if(cnt!=0) v.push_back(make_pair(p, cnt));
}
if(N != 1) {
v.push_back(make_pair(N, 1));
}
cout << "N의 소인수분해" << '\n';
for(int i=0; i<v.size(); ++i){
cout << v[i].first << '^' << v[i].second << '\n';
}
}참고 문제 : [boj.kr/7806, boj.kr/2312]
- 최대공약수 gcd(greatest common divisor)
최대공약수를 소인수 분해를 이용해서 하면, 시간이 매우 오래걸린다.
따라서 유클리드 호제법을 쓴다.
gcd(35, 25) = gcd(25, 10) = gcd(10, 15) = gcd(15, 10) = gcd(10, 5) = gcd(5, 5) = gcd(5,0) = 5.
이걸 살짝 변형해서 현대에는
gcd(35, 25) = gcd(25, 10) = gcd(10, 5) = gcd(5, 0) = 5.
식 : gcd(a, b) = gcd(b, a%b)이고, gcd(k, 0)일 때 답은 k ( 단, a, b, k가 양의 정수일 때)
int gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a%b);
}재귀함수로 구현 가능하다.
팁1 : 시간복잡도는 최악 O(log_10(N))이다. 하지만 정말 빠르기 때문에 O(1)이라고 과장해서 말할 수도 있다.
팁2 : a가 b보다 작아도 예외처리 안해도 된다.
- 최소공배수 lcm(least common multiple)
식은 lcm(a, b) = a/gcd(a,b) * b
long long lcm(int a, int b) {
return a/gcd(a, b) * b;
}팁1 : 오버플로우 조심해야한다.
팁2 : b/gcd(a,b) * a해도 동일하게 나온다.
참고 문제 : [boj.kr/2609, boj.kr/9613, boj.kr/1735]
- 에라토스테네스의 체(sieve)
소수 구하는 알고리즘. 2부터 sqrt(N)까지 i*i ~ N 구간 내에 있는 i의 모든 배수를 지운다. 끝나고 남은 숫자들이 모두 소수.
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 1e6; // 백만
bool isErased[MAX_N+1];
// sieve[p] == false : p가 아직 안지워졌다.
// sieve[p] == true : p가 지워졌다.
int main(){
int N; cin >> N;
isErased[0] = true;
isErased[1] = true;
for(int p=2; p*p <=N; ++p){
if(isErased[p]) continue;
for(int j=p*p; j<=N; j+=p){
isErased[j]=true;
}
}
while(true){
int K; cin >> K;
if(isErased[K]) cout << "소수 아님" << '\n';
else cout << "소수!" << '\n';
}
}시간 복잡도는 O(N * log(log N)). 사실상 O(N)
참고 문제 : [boj.kr/1978, boj.kr/1929, boj.kr/4948, boj.kr/1456, boj.kr/1676, boj.kr/2004]
- 부록 : 참고 문제 풀이
- boj.kr/17466
#include <iostream>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int N, P; cin >> N >> P;
int res = 1;
for(int i=1; i<=N; ++i){
res = (res * (long long)i) % P;
}
cout << res << '\n';
}- boj.kr/7806
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int> > v;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int N; cin >> N;
for(int p=2; p*p<=N; ++p){
int cnt=0;
while(N%p==0){
N/=p;
cnt++;
}
if(cnt!=0) v.push_back(make_pair(p, cnt));
}
if(N != 1) {
v.push_back(make_pair(N, 1));
}
for(int i=0; i<v.size(); ++i){
for(int j=0; j<v[i].second; ++j){
cout << v[i].first << '\n';
}
}
}- boj.kr/2312
#include <iostream>
#include <vector>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int T; cin >> T;
while(T--){
vector<pair<int, int> > v;
int N; cin >> N;
for(int p=2; p*p<=N; ++p){
int cnt=0;
while(N%p==0){
N/=p;
cnt++;
}
if(cnt!=0) v.push_back(make_pair(p, cnt));
}
if(N != 1) {
v.push_back(make_pair(N, 1));
}
for(int i=0; i<v.size(); ++i){
cout << v[i].first << ' ' << v[i].second << '\n';
}
}
}- boj.kr/2609
#include <iostream>
using namespace std;
int gcd(int a, int b){
if(!b) return a;
return gcd(b, a%b);
}
long long lcm(int a, int b){
return a/gcd(a, b) * b;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int a, b; cin >> a >> b;
cout << gcd(a,b) << '\n' << lcm(a,b) << '\n';
}- boj.kr/9613
#include <iostream>
using namespace std;
typedef long long int ll;
ll gcd(int a, int b){
if(b==0) return a;
return gcd(b, a%b);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll t; cin >> t;
while(t--){
ll n; cin >> n;
ll arr[101];
for(int i=0; i<n; ++i){
cin >> arr[i];
}
ll res=0;
for(int i=0; i<n-1; ++i){
for(int j=i+1; j<n; ++j){
res+=gcd(arr[i], arr[j]);
}
}
cout << res << '\n';
}
}- boj.kr/1735
#include <iostream>
using namespace std;
int gcd(int a, int b){
if(!b) return a;
return gcd(b, a%b);
}
int lcm(int a, int b){
return a/gcd(a,b) * b;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int a, b, c, d; cin >> a >> b >> c >> d;
int mo = lcm(b, d);
int ja = lcm(b, d)/d*c + lcm(b,d)/b*a;
cout << ja/gcd(mo, ja) << ' ' << mo/gcd(mo, ja) << '\n';
}- boj.kr/1978
#include <iostream>
using namespace std;
const int MAX_N = 1001;
bool isErased[MAX_N+1];
int main(){
ios_base::sync_with_stdio(false); cin.tie();
isErased[0] = true;
isErased[1] = true;
for(int p=2; p*p <=1000; ++p){
if(isErased[p]) continue;
for(int j=p*p; j<=1000; j+=p){
isErased[j]=true;
}
}
int N; cin >> N;
int cnt=0;
while(N--){
int a; cin >> a;
if(!isErased[a]) cnt++;
}
cout << cnt << '\n';
}- boj.kr/1929
#include <iostream>
using namespace std;
const int MAX_N = 1000001;
bool isErased[MAX_N+1];
int main(){
ios_base::sync_with_stdio(false); cin.tie();
isErased[0] = true;
isErased[1] = true;
for(int p=2; p*p <=MAX_N; ++p){
if(isErased[p]) continue;
for(int j=p*p; j<=MAX_N; j+=p){
isErased[j]=true;
}
}
int a, b; cin >> a >> b;
for(int i=a; i<=b; ++i){
if(!isErased[i]) cout << i << '\n';
}
}- boj.kr/4948
#include <iostream>
using namespace std;
const int MAX_N = 247000;
bool isErased[MAX_N+1];
int main(){
ios_base::sync_with_stdio(false); cin.tie();
isErased[0] = true;
isErased[1] = true;
for(int p=2; p*p <=MAX_N; ++p){
if(isErased[p]) continue;
for(int j=p*p; j<=MAX_N; j+=p){
isErased[j]=true;
}
}
while(1){
int a, cnt=0; cin >> a;
if(a==0) break;
for(int i=a+1; i<=2*a; ++i){
if(!isErased[i]) cnt++;
}
cout << cnt << '\n';
}
}- boj.kr/1456 ( long long 범위 벗어나는거 조심)
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
const int MAX_N = 1e7;
bool isErased[MAX_N+1];
int main(){
ll a, b;
cin >> a >> b;
isErased[0] = true;
isErased[1] = true;
for(ll p=2; p<=MAX_N; ++p){
if(isErased[p]) continue;
for(ll j=p*p; j<=MAX_N; j=j+p){
isErased[j]=true;
}
}
ll cnt = 0;
ll aa = sqrt(a);
for(ll p=2; p*p<=b; p=p+1){
if(!isErased[p]) {
for(ll k=p; p<=b/k; k=k*p){
if(k*p>=a) cnt = cnt + 1;
}
}
}
cout << cnt << '\n';
}- boj.kr/1676
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int N;
cin >> N;
int k=2;
int cnt2=0, cnt5=0;
while(k<=N){
cnt2+=N/k;
k*=2;
}
k=5;
while(k<=N){
cnt5+=N/k;
k*=5;
}
cout << min(cnt2, cnt5) << '\n';
}- boj.kr/2004
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll cnt2=0, cnt5=0;
void f(ll N){
ll k=2;
while(k<=N){
cnt2+=N/k;
k*=2;
}
k=5;
while(k<=N){
cnt5+=N/k;
k*=5;
}
}
void f2(ll N1, ll N2){
ll k=2;
while(k<=N1){
cnt2-=N1/k;
k*=2;
}
k=2;
while(k<=N2){
cnt2-=N2/k;
k*=2;
}
k=5;
while(k<=N1){
cnt5-=N1/k;
k*=5;
}
k=5;
while(k<=N2){
cnt5-=N2/k;
k*=5;
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll n, m;
cin >> n >> m;
f(n);
f2(m, n-m);
if(min(cnt2, cnt5)<=0){
cout << '0' << '\n';
}
else {
cout << min(cnt2, cnt5) << '\n';
}
}반응형