oj.uz

Submission #15432

# Submission time Handle Problem Language Result Execution time Memory
15432 2015-07-12T07:37:16 Z myungwoo 피보나미얼 (kriii3_V) C++14
74 / 74
 1273 ms 1092 KB 
#include<stdio.h>
#include<algorithm>

using namespace std;

typedef long long ll;

const int MX = 1000;

ll M;
ll DB[MX+5];

ll mul(ll A, ll B, ll M)
{
    if( M < 1ll<<31 ) return A*B%M;
    if( !B ) return 0;
    else return (mul((A<<10)%M, B>>10, M) + A*(B&((1<<10)-1)) )%M;
}

struct mat{
    ll t[2][2];
    mat operator*(const mat &l)const{
        mat ans;
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++){
                ans.t[i][j] = 0;
                for(int k = 0; k < 2; k++){
                    ans.t[i][j] += mul(t[i][k], l.t[k][j], M);
                }
                ans.t[i][j] %= M;
            }
        }
        return ans;
    }
};

ll get(ll N, ll P)
{
    M = P;
    mat mul = {1, 1, 1, 0}, ans = {1, 0, 0, 1};
    while(N){
        if(N%2) ans = ans * mul;
        mul = mul * mul, N /= 2;
    }
    return ans.t[1][0];
}

int main()
{
    int N, P;
    scanf("%d%d", &N, &P);
    for(int i = 2; i <= P; i++){
        if(DB[i]) continue;
        ll wi = 0, lst = 0, ans = 0, step = 1, lv = i;
        while(wi + step <= N){
            wi += step;
            if( get(wi, lv) == 0 ){
                step = wi; wi = 0;
                ans += N / step;
                lv *= i;
            }
        }
//        if( lv > 1ll << 40 ) printf("%d %lld\n", i, lv);
        DB[i] = ans;
        for(int j = i*2; j <= P; j += i) DB[j] = 1;
    }
    for(int i = 2; i <= P; i++){
        ll ans = 0x7fffffffffffffll, su = i;
        for(int j = 2; j <= su; j++){
            int cnt = 0;
            while(su%j == 0){
                su /= j;
                cnt++;
            }
            if( cnt ) ans = min(ans, DB[j] / cnt);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1092 KB Output is correct
2 Correct 5 ms 1092 KB Output is correct
3 Correct 5 ms 1092 KB Output is correct
4 Correct 5 ms 1092 KB Output is correct
5 Correct 6 ms 1092 KB Output is correct
6 Correct 6 ms 1092 KB Output is correct
7 Correct 51 ms 1092 KB Output is correct
8 Correct 90 ms 1092 KB Output is correct
9 Correct 110 ms 1092 KB Output is correct
10 Correct 105 ms 1092 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 1092 KB Output is correct
2 Correct 148 ms 1092 KB Output is correct
3 Correct 130 ms 1092 KB Output is correct
4 Correct 145 ms 1092 KB Output is correct
5 Correct 177 ms 1092 KB Output is correct
6 Correct 548 ms 1092 KB Output is correct
7 Correct 562 ms 1092 KB Output is correct
8 Correct 1273 ms 1092 KB Output is correct
9 Correct 1273 ms 1092 KB Output is correct
10 Correct 1272 ms 1092 KB Output is correct