Submission #19272

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19272	2016-02-23T17:20:31 Z	kaTkaHr	팔찌 (kriii4_V)	C++14	6 / 100	1000 ms	36244 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];

int main()
{
	int N, K;
	scanf("%d%d", &N, &K);
	phi[1] = 1;
	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] + pw(frac(K, 1), 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 + pw(frac(K, 1), i/2) * (K+1) / 4;
		else B[i] = P[i] / 2 + pw(frac(K, 1), 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	5 ms	36244 KB	Output is correct
2	Correct	8 ms	36244 KB	Output is correct
3	Correct	4 ms	36244 KB	Output is correct
4	Correct	0 ms	36244 KB	Output is correct
5	Correct	0 ms	36244 KB	Output is correct
6	Correct	0 ms	36244 KB	Output is correct
7	Correct	8 ms	36244 KB	Output is correct
8	Correct	7 ms	36244 KB	Output is correct
9	Correct	8 ms	36244 KB	Output is correct
10	Correct	4 ms	36244 KB	Output is correct
11	Correct	3 ms	36244 KB	Output is correct
12	Correct	0 ms	36244 KB	Output is correct
13	Correct	4 ms	36244 KB	Output is correct
14	Correct	4 ms	36244 KB	Output is correct
15	Correct	8 ms	36244 KB	Output is correct
16	Correct	0 ms	36244 KB	Output is correct
17	Correct	0 ms	36244 KB	Output is correct
18	Correct	0 ms	36244 KB	Output is correct
19	Correct	4 ms	36244 KB	Output is correct
20	Correct	8 ms	36244 KB	Output is correct

Subtask #2

0.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	36244 KB	Output is correct
2	Correct	4 ms	36244 KB	Output is correct
3	Correct	5 ms	36244 KB	Output is correct
4	Correct	202 ms	36244 KB	Output is correct
5	Execution timed out	1000 ms	36240 KB	Program timed out
6	Halted	0 ms	0 KB	-