Algorithm： Prime & Euler Function & Productive Function

소수 체
소박 한 알고리즘
일반적으로 시험 나눗셈 으로 어떤 수가 소수 인지 아 닌 지 를 판단 할 수 있다.

bool isPrime(int n) {
    if(n < 2) return false;
    for(int i = 2; i < n; i++)
        if(n % i == 0) return false;
    return true;
}

그러나 사실 우 리 는 근호 n 으로 만 제거 하면 된다. 왜냐하면 임의의 n 에 대해 근호 n 보다 큰 인수 가 존재 한다 고 가정 하면 근호 n 보다 작은 인수 와 대응 하 는 것 이 분명 하 다.그러면:

bool isPrime(int n) {
    if(n < 2) return false;
    int m = sqrt(n + .5);
    for(int i = 2; i <= m; i++)
        if(n % i == 0) return false;
    return true;
}

에이 체
그러나 우리 가 n 보다 작은 모든 수 를 요구한다 면 소 수 는 아 닐 까?이때 우 리 는 소수 체 법 으로 해결한다.체 법 은 일종 의 사상 으로 이전에 처 리 된 정 보 를 이용 하여 뒤의 결 과 를 갱신 하 는 것 이다.1 보다 큰 숫자 에 대해 그 배 수 는 분명히 합 수 이다. 그러면 우 리 는 i 에 옮 겨 다 닐 때 모든 i 의 배 수 를 걸 러 낼 수 있다.우리 가 i + 1 에 옮 겨 다 닐 때, 그것 이 아직 걸 리 지 않 았 다 면, 그것 은 반드시 소수 일 것 이다.이것 이 바로 엘 라 토스 테 니 체 법 으로 약칭 하여 엘 라 토스 테 니 체 라 고 한다.

int prime[M];
bool vis[M];
void eratosthenes() {
    for (int i = 2; i < M; i++) {
        if (!vis[i]) {
            prime[++prime[0]] = i;
            for (int j = 2 * i; j < M; j += i) {
                vis[j] = 1;
            }
        }
    }
}

에 스 체 개선
분명히 에 씨 체 는 반복 적 인 체 제 작업 이 많 고 소박 한 알고리즘 중의 최 적 화 를 에 씨 체 에 도입 하면 우 리 는 개 선 된 에 씨 체 를 얻 을 수 있다.

int prime[M];
bool vis[M];
void eratosthenes_plus() {
    int m = sqrt(M + .5);
    for (int i = 2; i <= m; i++) {
        if (!vis[i]) {
            prime[++prime[0]] = i;
            for (int j = i * i; j < M; j += i) {
                vis[j] = 1;
            }
        }
    }
}

오 라 체
개 선 된 에 씨 체 의 복잡 도 는 대부분 상황 에서 받 아들 일 수 있 지만 가끔 은 선형 시간 으로 1 ~ n 의 모든 소 수 를 판단 해 야 한다.이 럴 때 는 오 라 체 가 필요 하 다.오로라 체 는 모든 소수 가 가장 작은 (질) 인수 에 의 해 체 로 떨 어 질 것 을 보증 함으로써 복잡 도 를 선형 에 이 르 게 한다.

int prime[M];
bool vis[M];
void euler() {
    for(int i = 2; i < M; i++) {
        if(!vis[i]) {
            prime[++prime[0]] = i;
        }
        for(int j = 1; j <= prime[0] && i * prime[j] < M; j++) {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}

포 인 트 는 if (i% prime [j] = = 0) 에 있 습 니 다. 왜 i 가 j 번 째 소수 의 배수 일 때 체 제 를 멈 춰 야 합 니까? \[\ begin {align} & i 가 prime [j] 의 배수 일 때, 우 리 는 i 를 i = k \ \ times prime [j], k \ in N ^ + 로 표시 할 수 있다.각 수가 가장 작은 질량 인수 에 걸 리 는 원칙 에 맞 게 \ \ & 이 때 는 순환 을 뛰 어 넘 어야 한다. prime [j + 1] \ times (k \ times prime [j]) 로 X 를 걸 러 내지 않 고 앞으로 \ \ & prime [j] \ times (k \ times prime [j + 1]) 로 X 를 걸 러 내야 한다. \ end {align} \]
오로라 함수 와 오로라 의 정리
오로라 함수
수론 에서 정수 n, 오로라 함수φ(n) 의 값 은 n 보다 작 거나 같은 정수 에서 n 과 서로 질 적 인 수의 개수 이다.
예 를 들 면:φ(8) = 4 는 1, 3, 5, 7 과 8 의 상호 질 때문이다.
확장: 군 론 에서 오로라 함 수 는 실제 적 으로 모 n 의 동 여 류 로 구 성 된 곱셈 군의 단계 입 니 다.
오로라 정리
수론 에서 오 라 의 정 리 는 gcd (a, n) = 1 이면 \ [a ^ {\ phi (n)} \ \ equiv 1 (mod \ space n) \ \] 오 라 함수 의 성질 과 라 그 랑 일 동반 정리 가 결합 하여 오 라 의 정 리 를 증명 한다.
보급: 오로라 강 멱 공식 \ \ [a ^ b \ equiv a ^ {b \% \ phi (n) + \ phi (n)} (mod \ space n) \ \]
예제: 낙 곡 5091
성질
기본 성
n 이 질 p 의 k 차 멱 이면 \ [\ phi (n) = \ phi (p ^ k) = p ^ k - p ^ {k - 1} = (p - 1) p ^ {k - 1} \ \ \ \ \ p ^ {k - 1} 은 1 에서 n 중 p 의 배수 로 이 수 들 은 n 과 서로 질 이 맞지 않 는 것 이 분명 하 다. \ \] 예: \ [\ phi (72) = \ phi (2 ^ 3 \ times 3 ^ 2) = 2 ^ {3 - 1} \ times (2 - 1) \ times 3 ^ {2 - 1} \ times (3 - 1) \ \ times (3 - 1)
페 르 마 소정 리 의 보급
페 르 마 의 작은 정 리 를 되 돌아 본다: p 가 양수 이 고 a 가 임의의 정수 라면 \ \ [a ^ p - a 는 p 로 정 리 될 수 있다. \ \] 즉 \ [\ begin {aligned} & a ^ p - a \ equiv 0 (mod \ space p) \ \ \ \ \ \ Left rightarrow & a ^ p \ equiv a (mod \ space p) \ \ \ \ \ \ \ \ \ Left rightarrow & a ^ {p - 1} \ equiv 1 (mod \ space p) \ end {aligned} \] 은 오로라 의 정리 로 돌아간다.φ(p) = p - 1, 그러면 \ [a ^ {p - 1} \ equiv 1 (mod \ space p) \ \ \] 이것 이 바로 페 마 의 작은 정리 입 니 다.역사상 오 라 는 먼저 페 마 의 작은 정 리 를 증명 한 다음 에 이 를 바탕 으로 오 라 의 정 리 를 보급 했다.
적성 함수
즉 m, n 호 질φ（mn）=φ（m）φ（n）
홍보: n 보다 작은 모든 n 과 의 상호 질 적 인 수의 합 은 n * 입 니 다.φ（n）/2。
임의의 a > b > 0, gcd (a, b) = 1, 총 gcd (a, a - b) = 1.그러면φ(n) 개 는 n 보다 작은 수 와 n 의 상호 질 로 x 로 설정 하면 n - x 도 n 과 상호 질 이 존재 하고 이들 의 합 은 n 이 라면 모두 있다.φ(n) / 2 쌍.이 수의 합 은 n 이다.φ（n）/2。
예: hdu 3501
제목: n 보다 작은, n 과 서로 질 적 이지 않 은 수의 합% 1, 000, 000, 007 을 구하 고 그 중에서 n ≤ 10 의 9 차방 을 구한다.
오로라 함수 계산
정수 n 의 정수 n 에 대한 분해 질 인 수 는 다음 과 같 같 습 니 다. \ \ \ \ [n = p 1... \ \ \ [n = p {k 1} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ < < < < < < < < p (p ^ k)} \ \ \ \ \ < < < < < < < < < < < < < < < < < < < < < < < < < p}}} \ \ \ \ \ \ \ \.... \ \ \ \ < < < < < < < < < < p K}}}} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p 1 \ \ \......... \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2}) \ times... \ times p m ^ {k m} (1 - {1 \ \ over p m}) \ \] 또: \ [n = \ prod {i = 1} ^ m p i ^ {k i} \ \] 그래서: \ [\ phi (n)= n \ \ times \ \ prod {i = 1} ^ m (1 - {1 \ \ \ over p i}) \ \] 코드 는 다음 과 같 습 니 다. (예제: poj 2407)

//          
int euler(int n) {
    int ans = n;
    //               
    int m = sqrt(n + .5);
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            ans -= ans / i;
            while(n % i == 0) n/= i;
        }
    }
    if(n > 1) ans -= ans / n;
    return ans;
}

다음은 타 표 표기 법.

LL euler[N];
void cal_euler() {
    euler[1] = 1;
    for(int i = 2; i 

예문: hdu 2824
제목: 오로라 접두사 와.공간 제한 에 주의 하 세 요.

#include 
#include 
using namespace std;
typedef long long LL;
const int N = 3e6 + 100;
LL euler[N];
void pre() {
    euler[1] = 1;
    for(int i = 2; i > a >> b) {
        cout << euler[b] - euler[a - 1] << endl;
    }
    return 0;
}

적성 함수
정의.
수론 에서 적성 함 수 는 정수 집합 에 정 의 된 산수 함수 f (n) 를 가리 키 며 f (1) = 1 이 있다.만약 gcd (a, b) = 1, f (ab) = f (a) f (b).
확장: 완전 적성 함수: 만약 에 적성 함수 f 가 gcd (a, b) ≠ 1 일 때 f (ab) = f (a) f (b) 가 있 으 면 f 를 완전 적성 함수 라 고 부른다.수론 밖의 적성 함 수 는 일반적으로 완전 적성 함 수 를 가리킨다.
성질
n 질 인 에 대한 분해: \ \ [n = \ prod ^ k {i = 1} p i ^ {a i}, 그 중에서 p i 는 분 해 된 질 인수 \] 로 적 함수 f 에 대해 \ [f (n) = \ \ prod ^ k {i = 1} f (p i ^ {a i}) \] 가 있 습 니 다.
흔 한 적성 함수
오로라 함수, 모 비 우 스 함수, gcd (n, k) (k 고정), 약수 함수σ（σ(n) 은 n 의 약수 이다.약수 함수σ정 의 는 다음 과 같 습 니 다.
임의의 정수 n 에 대해 서 는 질량 인 을 \ [n = p 1 ^ {k 1} \ \ times p 2 ^ {k 2} \ times... \ \ times p m ^ {k m} \ \] 로 나 누 면 그 인수 개 수 는 \ [N = (k 1 + 1) \ \ times (k 2 + 1) \ \ times... \ times (k m + 1) \ \ \ \ times (k m + 1) \ \ \ \] 이다.
\ [즉:σ(n)=\prod_{i=1}^m (k_i+1) \]