oj.uz

Submission #15331

# Submission time Handle Problem Language Result Execution time Memory
15331 2015-07-12T06:15:39 Z myungwoo 피보나미얼 (kriii3_V) C++14
32 / 74
 342 ms 1092 KB 
#include<stdio.h>
#include<algorithm>

using namespace std;

typedef long long ll;

const int MX = 1000;

int M;
ll DB[MX+5];

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] += t[i][k] *l.t[k][j];
                }
                ans.t[i][j] %= M;
            }
        }
        return ans;
    }
};

int get(int 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;
            }
        }
        for(int j = i; j <= P; j += i) DB[j] = ans;
    }
    for(int i = 2; i <= P; i++){
        ll ans = 0x7fffffff;
        for(int j = 2; j <= i; j++){
            int cnt = 0, su = i;
            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 7 ms 1092 KB Output is correct
2 Correct 7 ms 1092 KB Output is correct
3 Correct 7 ms 1092 KB Output is correct
4 Correct 7 ms 1092 KB Output is correct
5 Correct 7 ms 1092 KB Output is correct
6 Correct 7 ms 1092 KB Output is correct
7 Correct 19 ms 1092 KB Output is correct
8 Correct 29 ms 1092 KB Output is correct
9 Correct 36 ms 1092 KB Output is correct
10 Correct 35 ms 1092 KB Output is correct

Subtask #2
0.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1092 KB Output is correct
2 Correct 49 ms 1092 KB Output is correct
3 Correct 42 ms 1092 KB Output is correct
4 Correct 47 ms 1092 KB Output is correct
5 Correct 56 ms 1092 KB Output is correct
6 Correct 169 ms 1092 KB Output is correct
7 Correct 169 ms 1092 KB Output is correct
8 Incorrect 342 ms 1092 KB Output isn't correct
9 Halted 0 ms 0 KB -