Submission #19273

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19273	2016-02-23T17:23:46 Z	kaTkaHr	팔찌 (kriii4_V)	C++14	100 / 100	964 ms	51868 KB

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.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	51868 KB	Output is correct
2	Correct	11 ms	51868 KB	Output is correct
3	Correct	3 ms	51868 KB	Output is correct
4	Correct	5 ms	51868 KB	Output is correct
5	Correct	0 ms	51868 KB	Output is correct
6	Correct	5 ms	51868 KB	Output is correct
7	Correct	3 ms	51868 KB	Output is correct
8	Correct	0 ms	51868 KB	Output is correct
9	Correct	5 ms	51868 KB	Output is correct
10	Correct	3 ms	51868 KB	Output is correct
11	Correct	3 ms	51868 KB	Output is correct
12	Correct	3 ms	51868 KB	Output is correct
13	Correct	3 ms	51868 KB	Output is correct
14	Correct	0 ms	51868 KB	Output is correct
15	Correct	7 ms	51868 KB	Output is correct
16	Correct	0 ms	51868 KB	Output is correct
17	Correct	7 ms	51868 KB	Output is correct
18	Correct	3 ms	51868 KB	Output is correct
19	Correct	5 ms	51868 KB	Output is correct
20	Correct	5 ms	51868 KB	Output is correct

Subtask #2

94.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	51868 KB	Output is correct
2	Correct	3 ms	51868 KB	Output is correct
3	Correct	10 ms	51868 KB	Output is correct
4	Correct	45 ms	51868 KB	Output is correct
5	Correct	518 ms	51868 KB	Output is correct
6	Correct	666 ms	51868 KB	Output is correct
7	Correct	495 ms	51868 KB	Output is correct
8	Correct	624 ms	51868 KB	Output is correct
9	Correct	751 ms	51868 KB	Output is correct
10	Correct	900 ms	51868 KB	Output is correct
11	Correct	735 ms	51868 KB	Output is correct
12	Correct	851 ms	51868 KB	Output is correct
13	Correct	459 ms	51868 KB	Output is correct
14	Correct	834 ms	51868 KB	Output is correct
15	Correct	431 ms	51868 KB	Output is correct
16	Correct	542 ms	51868 KB	Output is correct
17	Correct	942 ms	51868 KB	Output is correct
18	Correct	489 ms	51868 KB	Output is correct
19	Correct	629 ms	51868 KB	Output is correct
20	Correct	964 ms	51868 KB	Output is correct