[COCI 12/13 #1] SNAGA(숫자의 힘)

문제 링크

플4치고 쉬운? 문제

풀이

2

3→2

4→3→2

5→2

6→4→3→2

7→2

8→3→2

9→2

10→3→2

 

주어진 수를 나누지 않는 최솟값 → 어떤 수보다 미만의 모든 수가 주어진 수를 나누게 하는 최솟값

따라서

$$|\{k|(2\nmid k)\}|\times (strength(2)+1)\\+\\ |\{k|(2\mid k)\wedge(3\nmid k)\}|\times (strength(3)+1)\\+\\ |\{k|(2\mid k)\wedge (3\mid k)\wedge (4\nmid k)\}|\times (strength(4)+1)\\+\\ \vdots$$

를 구해주면 된다.

$\mathrm{lcm}$ 단위로 커지기 때문에, 전처리할 $strength(k)$의 종류가 그리 많지 않다는 것을 알 수 있다.

실제로 해보면 42인가까지가 딱 맞다. 넘기면 오버플로우 나는 딱 그런 지점이더라.

 

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)

ll a, b;
ll d[43], l[43];

int main() {
    scanf("%lld %lld", &a, &b);
    d[1] = 1;
    rep(i,2,42) d[i] = lcm(i,d[i-1]);
    l[2] = 1;
    rep(i,3,42) {
        rep(j,2,42) {
            if (i%d[j] != 0) {
                l[i] = l[j]+1;
                break;
            }
        }
    }
    ll w = b-a+1, ans = 0;
    rep(i,2,42) {
        ll v = b/d[i]-(a-1)/d[i];
        ans += (w-v)*(l[i]+1);
        w = v;
    }
    printf("%lld", ans);
}