[BOJ 16409] Coprime Integers

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

16409번: Coprime Integers

 

- 문제 요약

 

구간 [a, b]와 [c, d]가 주어졌을 때, a ≤ x ≤ b 및 c ≤ y ≤ d가 되는 공동 소수 정수(x, y)의 순서쌍의 수를 세십시오. 서로소 정수는 1보다 큰 공통 인수를 갖지 않습니다.

 

 

- 알고리즘 정리

 

https://panty.run/boj8291/

BOJ 8291 Coprime Numbers

이 분의 블로그를 참고해서 풀었습니다.

arr[i] : gcd(x, y)가 i의 배수인 쌍의 개수

brr[i] : gcd(x, y)가 i인 쌍의 개수

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 10000001
typedef long long ll;
ll a,b,c,d,arr[MAX],brr[MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>a>>b>>c>>d;
	a--;
	c--;
	for(int i=1;i<=MAX-1;i++){
		arr[i]=(b/i-a/i)*(d/i-c/i);
	}
	for(int i=MAX-1;i>=1;i--){
		brr[i]=arr[i];
		for(int j=2*i;j<=MAX-1;j+=i){
			brr[i]-=brr[j];
		}
	}
	cout<<brr[1];
}

코드 제출 결과