Submission #19273

#	Time	Username	Problem	Language	Result	Execution time	Memory
19273		kaTkaHr	팔찌 (kriii4_V)	C++14	100 / 100	964 ms	51868 KiB

V

#include <stdio.h>
#include<vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MX = 1000005, MM = 1000000007;

ll pw(ll A, ll B){
    ll R = 1;
    while(B){
        if( B&1 ) R = R * A % MM;
        A = A * A % MM; B /= 2;
    }
    return R;
}


ll rv(ll A){ return pw(A, MM-2); }

struct frac{
    ll A, B;
		frac(ll A):A(A), B(1){}
    frac(ll a, ll b){
        A = (a%MM+MM) % MM;
        B = (b%MM+MM) % MM;
    }
    frac(){A = 0, B = 1;}
    frac operator+ (const frac &l)const{
        return frac((A * l.B + B * l.A) % MM, B * l.B % MM);
    }
    frac operator*(const frac &l)const{
        return frac(A*l.A % MM, B*l.B % MM);
    }
    frac operator/(const frac &l)const{
        return frac(A*l.B % MM, B*l.A % MM);
    }
    frac operator- (const frac &l)const{
        return frac((A*l.B - B*l.A%MM + MM) % MM, B*l.B % MM);
    }
    ll v(){ return A * rv(B) % MM; }
};

frac pw(frac A, ll B){
    frac R = 1;
    while(B){
        if( B&1 ) R = R * A;
        A = A * A; B /= 2;
    }
    return R;
}

int phi[MX];
frac P[MX], B[MX], Q[MX];

int main()
{
	int N, K;
	scanf("%d%d", &N, &K);
	phi[1] = 1;
	Q[0] = 1;
	for(int i = 1; i <= N; i++) Q[i] = Q[i-1] * K;
	for(int i = 2; i <= N; i++){
		if( phi[i] ) continue;
		phi[i] = i-1;
		for(int j = 2*i; j <= N; j += i){
			if( j/i%i == 0 ) phi[j] = phi[j/i] * i;
			else phi[j] = phi[j/i] * (i-1);
		}
	}
	for(int i = 1; i <= N; i++){
		for(int j = i; j <= N; j += i){
			P[j] = P[j] + Q[j/i] * phi[i];
		}
	}
	for(int i = 1; i <= N; i++) P[i] = P[i] * frac(1, i);

	for(int i = 1; i <= N; i++){
		if( i % 2 == 0 ) B[i] = P[i] / 2 + Q[i/2] * (K+1) / 4;
		else B[i] = P[i] / 2 + Q[i/2+1] / 2;
	}
	frac ans = 1;
	for(int i = 1; i <= N; i++) ans = ans + B[i];
	printf("%lld\n", ans.v());
}

• Subtask 1: 6 / 6
• Subtask 2: 94 / 94