12개의 댓글이 있습니다.

• 
  일루

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

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

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

  링크 등을 참조해보세요.

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

  
  10년 전 link

• 
  Jaekwan

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

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

  
  10년 전 link

• 
  Being

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

  
  10년 전 link

• 
  일루

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

  
  10년 전 link

• 
  Being

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

  
  10년 전 link

• 
  infoefficiency

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

  
  10년 전 link

• 
  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;
      }
  }
  

  
  10년 전 link

• 
  Jaekwan

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

  
  10년 전 link

• 
  Jaekwan

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

  
  10년 전 link

• 
  RiKang

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

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

  
  10년 전 link

• 
  Jaekwan

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

  
  10년 전 link

• 
  Jaekwan

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

  
  10년 전 link

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