POJ 3358 Period of an Infinite Binary Expansion ★ (수론 좋 은 문제: 오로라 함수)

제목 링크:
http://poj.org/problem?id=3358
제목: 실제 점수 p / q 를 지정 하고 이 표시 에서 순환 시작 점 과 순환 절 길 이 를 구 합 니 다: {
x} = 0.
a
1
a
2...
ar(
a
r+1
a
r+2...
a
r+s)
w   우 리 는 1 / 10 이라는 데 이 터 를 관찰 할 수 있 습 니 다. 2 진 변환 법 (곱 하기 2 법) 에 따라 우 리 는 1 / 10 을 얻 을 수 있 습 니 다.  2 / 10 4 / 10 8 / 10 16 / 10 32 / 10... 그리고 모두 분자 모형 10, 획득: 1 / 10  2 / 10 4 / 10 8 / 10 6 / 10 2 / 10... 이때 반복 되 는 것 을 발견 하면
이 중복 은 우리 가 요구 하 는 최소 순환 이다. 
규칙 일반화: 주어진 p / q 에 대해 우 리 는 먼저 그것 을 가장 간단 한 점수, 즉 gcd (p, q) = 1 로 바 꿉 니 다. 그러면 우 리 는 p * 2 ^ i = p * 2 ^ j (mod q) 를 찾 아야 합 니 다. 이렇게 하면 순환 절 을 찾 을 수 있 습 니 다. gcd (p, q) = 1 이기 때문에 간 모 방정식 을 만 들 수 있 습 니 다. 2 ^ i * (2 ^ (j - i) - 1) = 0 (mod q)
2 ^ (j - i) - 1 은 홀수 이기 때문에 i = (q 의 인자 중 2 의 개수).Φ(i) = 1 (mod q ') 이 므 로 반드시 해 가 있 을 것 이다.그리고 정리 로 알 수 있다.
만약 a, p 호 질, 그리고 a ^ x = 1 (mod p) 이 있다 면 반드시 x |Φ(p). 따라서 마지막 으로 phi (i) 의 인 자 를 매 거 하면 됩 니 다. 

#include 
 
   
    
  
#include 
  
    
      #include 
     
       using namespace std; long long gcd(long long a, long long b){ return b ? gcd(b, a%b) : a; } long long phi(long long n){ long long res = n; for (int i = 2; i * i <= n; i ++){ if (n % i == 0){ res = res / i * (i - 1); while(n % i == 0) n /= i; } } if (n > 1){ res = res / n * (n - 1); } return res; } unsigned long long quick_add_mod(unsigned long long a, unsigned long long b, unsigned long long m){ unsigned long long res = 0, tmp = a % m; while(b){ if (b & 1) { res = res + tmp; res = (res >= m ? res - m : res); //     mod  } b >>= 1; tmp <<= 1; tmp = (tmp >= m ? tmp - m : tmp); } return res; } long long exp_mod(long long a, long long b, long long m){ long long res = 1 % m, tmp = a % m; while(b){ if (b & 1){ res = quick_add_mod(res, tmp, m); } tmp = quick_add_mod(tmp, tmp, m); b >>= 1; } return res; } vector 
      
        factor; void Factor(long long n){ factor.clear(); factor.push_back(1); factor.push_back(n); for (int i = 2; i * i <= n; i ++){ if (n % i == 0){ factor.push_back(i); factor.push_back(n / i); } } } int main(){ long long p, q, caseo = 1; while(scanf("%I64d%*c%I64d", &p, &q) == 2){ //       long long tmp_g = gcd(p, q); p /= tmp_g; q /= tmp_g; long long first_bit = 1; long long tmp_q = q; while(tmp_q % 2 == 0){ first_bit ++; tmp_q >>= 1; } long long length = 0; Factor(phi(tmp_q)); vector 
       
         :: iterator it = factor.begin(); sort(it, it+factor.size()); for (size_t i = 0; i < factor.size(); i ++){ //printf("%d
", factor[i]); if (exp_mod(2, factor[i], tmp_q) == 1){ length = factor[i]; break; } } printf("Case #%I64d: %I64d,%I64d
", caseo ++, first_bit, length); } return 0; }