두 수의 GCD가 1인 경우 구하기

  • Jaekwan
    Jaekwan

    어떤 한 문제에 골머리를 썩고 있네요. 쉬운것 같기도 하면서 너무 어렵습니다.
    두 숫자가 주어졌을때 그 숫자 아래로 모든 숫자 조합 중 GCD가 1인 경우를 찾고 있습니다.

    가령,
    3, 2가 주어졌다면 답은 5가 됩니다.
    (1,1) - GCD = 1
    (2,1) - GCD = 1
    (1,2) - GCD = 1
    (3,1) - GCD = 1
    (3,2) - GCD = 1

    그런데 두 수 A와 B의 제한이
    1<=A<=100000
    1<=B<=100000
    이기 때문에 모든 조합을 구하려고 하면 자꾸 제동이 걸리네요..

    O(NM)을 깨야 하는데 쉽지가 않네요..


    6년 전
12개의 댓글이 있습니다.
  • 일루
    일루

    엄청나게 쉬운 문제는 아닙니다.

    'count gcd 1' 을 검색하면 나오는

    http://math.stackexchange.com/questions/108483/number-of-pairs-a-b-with-gcda-b-1

    링크 등을 참조해보세요.

    totient function을 쓰는 방법과 Möbius function을 쓰는 두 가지 방법이 있습니다. 전 주로 후자를 사용합니다만...


    6년 전 link
  • Jaekwan
    Jaekwan

    아.. 꽤나 수학적인 문제인가 보군요..

    오늘 하루 종일 매달렸는데.. 수학용어 문맹이라..ㅜㅜ


    6년 전 link
  • Being
    Being

    a \neq b라서 저 링크보다 좀 더 어렵습니다.


    6년 전 link
  • 일루
    일루

    a=b면 gcd(a,b)=a인데 차이가 없을 것 같네요.


    6년 전 link
  • Being
    Being

    범위를 생각해야 되는데, \phi(n)n 미만의 서로소인 수로 정의되기 때문에.. i \in \{1, 2, \cdots, a\}i에 대해 b와 서로소인 개수를 세는 문제는 조금 더 생각해 보아야 하죠.


    6년 전 link
  • infoefficiency
    infoefficiency

    으.... 알고싶은데 너무 어렵네요 ㅠㅠ


    6년 전 link
  • Jaekwan
    Jaekwan

    ㅠ_ㅠ 제가 할 수 있는 최선의 코드를 잤는데 시간이 오버가 되는군요..

    이곳에 최적화 가능성이 있을까요??

    // 유클리드 gcd를 역으로 타서 
    // p = q+p로 재귀를 돌렸어요. 무조건 1인 것만 찾고 점프 하도록..
    // 결과값은 제대로 나오는데, 시간이 문제네요..
    
    <spoil>
    #include<iostream>
    #include<string>
    using namespace std;
    
    int total(int a, int b, int left, int right) {
        if (left > a || right >b){
            return 1;
        }
        return total(a,b,left+right,right) + total(a,b,left, left+right) ;
    }
    
    int main() {
        int t;
        int a,b;
        int ans;
    
        cin>>t;
        while(t--) {
            cin>>a>>b;
            ans = total(a,b,1,1) -1;
            cout<<ans<<endl;
        }
    }
    


    6년 전 link
  • Jaekwan
    Jaekwan

    나름 엘레강스한 방식이라고 생각해내서 좋아했는데.. 그냥 느리군요. ㅜ_ㅜ


    6년 전 link
  • Jaekwan
    Jaekwan

    Being님이 말씀하신 것(i∈{1,2,⋯,a}인 i에 대해 b와 서로소인 개수)처럼 n까지 정수 중 서로소인 k를 찾는 문제와 차이가 있네요. 계속 이부분에 막혀있기도 하구요.
    루프를 전부 돌면서 최적화 하는 방법밖에 없는것 일까요?
    소수를 다 찾아 놓고 가능하면 약수도 찾아 놓아서 루프도는 시간으로 최소로 하는 것 같은...계속 의문이 생기는 건 두 수가 모두 최대값 100000에 근접하면 10^10의 경우의 수중 많이 줄여도 얼마 되지 않을 것 같아서 고민이네요.


    6년 전 link
  • RiKang
    RiKang

    i∈{1,2,⋯,a}인 i에 대해 b와 서로소인 개수
    = P1,P2, ...,Pm 중 어떤 수로도 나누어 떨어지지 않는 i의 개수
    (P1,...,Pm = b 의 소인수)

    이런식으로 생각하면 b<=100000 때문에 m 이 작아서 가능할 듯 합니다.


    6년 전 link
  • Jaekwan
    Jaekwan

    @RiKang 약간 미묘한 차이가 있는데 가령, b의 원소중 Pi=15(소인수 3*5)은 a의 원소로 나누어 떨어지기 때문에 갯수 에서 빼야 하지만, gcd(2,15)=1이기 때문에 갯수에 합해야 합니다.


    6년 전 link
  • Jaekwan
    Jaekwan

    끝내 풀었내요. 감사합니다 =)

    먼저, a < b 일때, a가 소수와 소수가 아닌 경우로 나누어서
    i) 소수인경우는 b의 갯수에서 a의 배수를 없애서 더해 줬습니다.
    ii) 소수가 아닌경우는 b-(소인수의 조합) 으로 구했습니다.
    소인수의 조합을 구해서 빼는 경우의 수를 가늠하기가 어렵지만, 최대값의 경우 1분 넘게 걸리던 계산이 1-2초대로 줄었군요.


    6년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.