Submission #15432

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

V

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