답안 #19273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19273 2016-02-23T17:23:46 Z kaTkaHr 팔찌 (kriii4_V) C++14
100 / 100
964 ms 51868 KB
#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());
}
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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