Submission #15331

#	Time	Username	Problem	Language	Result	Execution time	Memory
15331		myungwoo	피보나미얼 (kriii3_V)	C++14	32 / 74	342 ms	1092 KiB

V

#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 / 32
• Subtask 2: 0 / 42