Submission #19851

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19851	2016-02-25T06:15:59 Z	tonyjjw	팔찌 (kriii4_V)	C++14	100 / 100	663 ms	54220 KB

V

//*
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <functional>
#define MOD 1000000007
#define MAX 0x3f3f3f3f
#define MAX2 0x3f3f3f3f3f3f3f3fll
#define ERR 1e-10
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#pragma warning(disable:4996)
using namespace std;

typedef long long ll;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

int n, m;
ll pi[1040000];
ll powm[1040000];
int comp[1040000];
ll xans[1040000];
ll inv[2040000];
ll xsum[1040000];

ll mul_inv(ll a, ll b=MOD)
{
	ll b0=b, t, q;
	ll x0=0, x1=1;
	if(b == 1) return 1;
	while(a > 1)
	{
		q=a/b;
		t=b, b=a%b, a=t;
		t=x0, x0=x1-q*x0, x1=t;
	}
	if(x1 < 0) x1+=b0;
	return x1;
}


ll modpow(ll x, ll y)
{
	ll ans=1;
	while(y)
	{
		if(y%2) ans*=x, ans%=MOD;
		x*=x, x%=MOD, y/=2;
	}
	return ans;
}

int main()
{
	int i, j, k;
	cin>>n>>m;
	//int t=clock();
	for(i=1;i<=n;i++) pi[i]=i;
	powm[0]=1;
	for(i=1;i<=n;i++) powm[i]=powm[i-1]*m, powm[i]%=MOD;
	for(i=1;i<=n*2;i++) inv[i]=mul_inv(i);
	ll ans=0;
	for(i=1;i<=n;i++)
	{
		xsum[i]=powm[i]*inv[i]%MOD;
	}
	for(i=1;i<=n;i++) xsum[i]+=xsum[i-1], xsum[i]%=MOD;
	for(i=1;i<=n;i++)
	{
		ll u=0;
		int k=1;
		for(j=i;j<=n;j+=i)
		{
			if(j != i && i >= 2) comp[j]=1;
			if(i >= 2 && !comp[i])
			{
				pi[j]/=i, pi[j]*=i-1;
			}
			//u+=powm[k++]*inv[j*2]%MOD;
		}
		u+=xsum[n/i]*inv[2*i]%MOD;
		//u%=MOD;
		ans+=pi[i]*u%MOD;
	}
	ans%=MOD;
	for(i=1;i<=n;i++)
	{
		if(i%2 == 0)
		{
			ans+=inv[4]*(m+1)%MOD*powm[i/2]%MOD;
		}
		else
		{
			ans+=inv[2]*powm[(i+1)/2]%MOD;
		}
	}
	ans++;
	ans%=MOD;
	cout<<ans;
	return 0;
}
//*/

Subtask #1

6.0 / 6.0

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

Subtask #2

94.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	54220 KB	Output is correct
2	Correct	0 ms	54220 KB	Output is correct
3	Correct	2 ms	54220 KB	Output is correct
4	Correct	31 ms	54220 KB	Output is correct
5	Correct	394 ms	54220 KB	Output is correct
6	Correct	485 ms	54220 KB	Output is correct
7	Correct	377 ms	54220 KB	Output is correct
8	Correct	474 ms	54220 KB	Output is correct
9	Correct	537 ms	54220 KB	Output is correct
10	Correct	631 ms	54220 KB	Output is correct
11	Correct	544 ms	54220 KB	Output is correct
12	Correct	613 ms	54220 KB	Output is correct
13	Correct	352 ms	54220 KB	Output is correct
14	Correct	597 ms	54220 KB	Output is correct
15	Correct	327 ms	54220 KB	Output is correct
16	Correct	408 ms	54220 KB	Output is correct
17	Correct	663 ms	54220 KB	Output is correct
18	Correct	379 ms	54220 KB	Output is correct
19	Correct	473 ms	54220 KB	Output is correct
20	Correct	662 ms	54220 KB	Output is correct