Problem 429 : Sum of squares of unitary divisors (20%)

Description

original

A unitary divisor d of a number n is a divisor of n that has the property gcd(d, n/d) = 1. The unitary divisors of 4! = 24 are 1, 3, 8 and 24. The sum of their squares is $1^2 + 3^2 + 8^2 + 24^2 = 650$.

Let S(n) represent the sum of the squares of the unitary divisors of n. Thus S(4!)=650.

Find S(100 000 000!) modulo 1 000 000 009.

간략해석

n = 100 000 000!의 인수중 $gcd(d, n/d) = 1$을 만족하는 d들의 제곱의 합을 구하라. (mod 1e9+9)

Idea & Algorithm

naive idea

일단 100000000!을 생으로 소인수 분해하여 gcd를 구하는 방법은 무리이다. 그렇다면 $d$ 와 $n/d$의 관계에 대해서 생각해보자.

$gcd(d, n/d) \neq 1$이라는 것은 $d$와 $n/d$이 하나 이상 공통 소인수를 가지고 있다는 것을 의미한다.

그렇기에 위 조건을 만족하기 위해서는 n의 소인수는 $d$또는 $n/d$에 모두 몰려있어야 한다.

100000000!의 소인수는 100000000이하 이고, 100000000 내의 소수는 1,000,0000 개 이하다. (이 부분에 대해서는 소수정리를 참고하면 된다.)

그렇다면 이 10,000,000개 가량의 소인수를 어떤 식으로 구성해주어야 할까?

advanced idea

N(=$10^8$)!을 소인수분해하면 다음과 같은 형태로 나올 것이다.

\[N! = {p_1}^{e_1}\cdot {p_2}^{e_2}...{p_k}^{e_k}.. (p_k < N 을 만족하는 소수)\]

그리고 $d$가 위 조건을 만족하기 위해서 $p_k$라는 소수가 포함되기 위해서는 반드시 ${p_k}^{e_k}$형태로 포함된다. ( $N!$에서 $e_k$의 값은 다음과 같음을 알고있다. $e_k = \sum_{i=1} \lfloor \frac{N}{ {p_k}^i }\rfloor$ )

따라서 $d$는 $p_k$라는 소인수를 ${p_k}^0(=1)$ 또는 ${p_k}^{e_k}$의 형태로 가지게 된다.

문제에서 요구하는 값은 모든 $d$의 제곱의 합이므로, 합을 구할때는 ${p_k}^{2\cdot e_k}$으로 계산하면 된다. 따라서 ${p_k}$의 포함 여부에 따른 성질로 다음과 같은 점화식을 쓸 수 있다.

\[f(n) = 위 조건을 만족하는 d 제곱의 합\] \[f({p_k}^{e_k}) = 1 + {p_k}^{2\cdot e_k}\] \[f(n \cdot {p_x}^{e_x}) = (1+{p_x}^{2\cdot e_x}) \cdot f(n) (단, n과 p_x는 서로소)\]

점화식을 연장하면 답은 다음 식으로 표현될 수 있다.

\[ANS = \prod_{k} (1+{p_k}^{2\cdot e_k})\]

source code

1억까지 수 중 소수를 모두 찾기 위해 그나마 에라토스테네스 체를 사용하였다. 소수를 찾은 동시에 정답값을 계산을 했다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const ll SZ = 1e8;
const ll MOD = 1e9+9;

ll ans = 1;

bool arr[SZ+1];

ll power(ll a, ll b, ll mod){
  ll ret = 1;
  while(b){
    if(b&1) ret = ret * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ret;
}

void era(){
  for(ll i = 2 ; i <= SZ ; i++){
    if(arr[i]) continue;
    ll cnt = 0;
    ll m = SZ;
    while(m){
      cnt += m/i;
      m /= i;
    }
    ans = ans * (power(i, cnt*2, MOD) + 1) % MOD;
    for(ll j = i*i ; j <= SZ ; j+= i){
      arr[j] = true;
    }
  }
}

int main(){
  era();
  cout << ans;
}

Problem 429