Problem:


Score : 1000 points

Problem Statement

Takahashi and Aoki are going to together construct a sequence of integers.

First, Takahashi will provide a sequence of integers a, satisfying all of the following conditions:

The length of a is N.

Each element in a is an integer between 1 and K, inclusive.

a is a palindrome, that is, reversing the order of elements in a will result in the same sequence as the original.

Then, Aoki will perform the following operation an arbitrary number of times:

Move the first element in a to the end of a.

How many sequences a can be obtained after this procedure, modulo 10^9+7?

Constraints

1≤N≤10^9

1≤K≤10^9

Input

The input is given from Standard Input in the following format:

N K

Output

Print the number of the sequences a that can be obtained after the procedure, modulo 10^9+7.

Sample Input 1

4 2

Sample Output 1

6

The following six sequences can be obtained:

(1, 1, 1, 1)

(1, 1, 2, 2)

(1, 2, 2, 1)

(2, 2, 1, 1)

(2, 1, 1, 2)

(2, 2, 2, 2)

Sample Input 2

1 10

Sample Output 2

10

Sample Input 3

6 3

Sample Output 3

75

Sample Input 4

1000000000 1000000000

Sample Output 4

875699961



Sample input:
4 2


Sample output:
6

Submission status: Wrong Answer

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,K = MI()
mod = 10**9+7

def divisor(n):  # nの約数のリスト
    res = []
    for i in range(1,int(n**.5)+1):
        if n % i == 0:
            res.append(i)
            if i != n//i:
                res.append(n//i)
    return res

A = divisor(N)

d = {}  # d[i] = iの約数のリスト(iはNの約数)
for a in A:
    d[a] = divisor(a)

prime = []  # Nの素因数のリスト
for i in range(2,int(N**.5)+1):
    if N % i == 0:
        prime.append(i)
        while N % i == 0:
            N //= i
if N != 1:
    prime.append(N)

mu = {}  # mu[i] = μ(i) (iはNの約数)
for a in A:
    b = a
    r = 1
    for p in prime:
        if b % p == 0:
            r *= -1
            if b//p % p == 0:
                r = 0
                break
    mu[a] = r


ans = 0
for a in A:
    for b in d[a]:
        if a % 2 == 0:
            ans += mu[a//b]*pow(K,(b+1)//2,mod)*(a//2)
            ans %= mod
        else:
            ans += mu[a//b]*pow(K,(b+1)//2,mod)*a

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k = map(int,readline().split())
MOD = 10**9+7

def divisor_list(N): #約数のリスト
    if N == 1: return [1]
    res = []
    for i in range(1,N):
        if i*i >= N: break
        if N%i == 0:
            res.append(i)
            res.append(N//i)
    if i*i == N: res.append(i)
    return sorted(res)



if n&1:
    p = [1] + [i for i in divisor_list(n)]
    
    r = {pi:pow(k,(pi+1)//2,MOD) for pi in p}
    for pi in p:
        for pj in p:
            if pj >= pi: break
            if pi%pj==0:
                r[pi] -= r[pj]

    #print(r)
    ans = 0
    for pi,v in r.items():
        ans += v*(pi)
    ans %= MOD
    print(ans)
    
    

else:
    p = [1] + [i for i in divisor_list(n) if i%2==0 and i!=2]
    
    r = {pi:pow(k,(pi+1)//2,MOD) for pi in p}
    for pi in p:
        for pj in p:
            if pj >= pi: break
            if pi%pj==0:
                r[pi] -= r[pj]

    #print(r)
    ans = 0
    for pi,v in r.items():
        if pi==1:
            ans += v
        else:
            ans += v*(pi//2)
    ans %= MOD
        
        
    print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k = map(int,readline().split())
MOD = 10**9+7

if n&1:
    ans = k + (pow(k,(n+1)//2,MOD)-k)*n
    print(ans%MOD)

else:
    def divisor_list(N): #約数のリスト
        if N == 1: return [1]
        res = []
        for i in range(1,N):
            if i*i >= N: break
            if N%i == 0:
                res.append(i)
                res.append(N//i)
        if i*i == N: res.append(i)
        return sorted(res)

    p = [1] + [i for i in divisor_list(n) if i%2==0 and i!=2]
    
    r = {pi:pow(k,(pi+1)//2,MOD) for pi in p}
    for pi in p:
        for pj in p:
            if pj >= pi: break
            if pi%pj==0:
                r[pi] -= r[pj]

    #print(r)
    ans = 0
    for pi,v in r.items():
        if pi==1:
            ans += v
        else:
            ans += v*(pi//2)
    ans %= MOD
        
        
    print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 +7

def main():
    n, k = map(int, input().split())
    if n % 2 == 0:
        ans = pow(k, n // 2, mod) * (n // 2)
        ans -= k * (n // 2 - 1)
    else:
        ans = pow(k, (n + 1) // 2, mod) * n
        ans -= k * (n - 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
M = 10**9+7
### 約数列挙
def fs(n):
    s = set()
    for i in range(1,int(n**0.5)+2):
        if n%i==0:
            s.add(i)
            s.add(n//i)
    l = sorted(list(s))
    return l
ds = fs(n)
m = len(ds)
nums = [None]*m
for i in range(m):
    val = pow(k, (ds[i]+1)//2, M)
    for j in range(i):
        if ds[i]%ds[j]==0:
            val -= nums[j]
            val %= M
    nums[i] = val%M
ans = 0
inv2 = pow(2, M-2, M)
for i in range(m):
    if ds[i]%2==0:
        ans += ds[i]*nums[i]*inv2
    else:
        ans += ds[i]*nums[i]
    ans %= M
print(ans%M)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,K = MI()
mod = 10**9+7

def divisor(n):  # nの約数のリスト
    res = []
    for i in range(1,int(n**.5)+1):
        if n % i == 0:
            res.append(i)
            if i != n//i:
                res.append(n//i)
    return res

A = divisor(N)

d = {}  # d[i] = iの約数のリスト(iはNの約数)
for a in A:
    d[a] = divisor(a)

prime = []  # Nの素因数のリスト
for i in range(2,int(N**.5)+1):
    if N % i == 0:
        prime.append(i)
        while N % i == 0:
            N //= i
if N != 1:
    prime.append(N)

mu = {}  # mu[i] = μ(i) (iはNの約数)
for a in A:
    b = a
    r = 1
    for p in prime:
        if b % p == 0:
            r *= -1
            if b//p % p == 0:
                r = 0
                break
    mu[a] = r


ans = 0
for a in A:
    for b in d[a]:
        if a % 2 == 0:
            ans += mu[a//b]*pow(K,(b+1)//2,mod)*(a//2)
            ans %= mod
        else:
            ans += mu[a//b]*pow(K,(b+1)//2,mod)*a
            ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

def divisors(M):#Mの約数列 O(n^(0.5+e))
    d=[]
    i=1
    while M>=i**2:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

mod=10**9+7
N,K=map(int,input().split())
div=divisors(N)

res=[0 for i in range(len(div))]
ans=0
if N%2==0:
    for i in range(len(div)):
        d=div[i]
        g=gcd(2*d,N)
        res[i]+=pow(K,g//2,mod)
        res[i]%=mod
        ans+=d*res[i]
        ans%=mod
        for j in range(i+1,len(div)):
            if div[j]%d==0:
                res[j]-=res[i]
                res[j]%=mod

    print(ans%mod)
else:
    for i in range(len(div)):
        d=div[i]
        g=gcd(2*d,N)
        res[i]+=pow(K,(g+1)//2,mod)
        res[i]%=mod
        ans+=d*res[i]
        ans%=mod
        for j in range(i+1,len(div)):
            if div[j]%d==0:
                res[j]-=res[i]
                res[j]%=mod

    print(ans%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k = map(int,readline().split())
MOD = 10**9+7

def divisor_list(N): #約数のリスト
    if N == 1: return [1]
    res = []
    for i in range(1,N):
        if i*i >= N: break
        if N%i == 0:
            res.append(i)
            res.append(N//i)
    if i*i == N: res.append(i)
    return sorted(res)



if n&1:
    p = [i for i in divisor_list(n)]
    r = {pi:pow(k,(pi+1)//2,MOD) for pi in p}
    #print(r)
    for pi in p:
        for pj in p:
            if pj >= pi: break
            if pi%pj==0:
                r[pi] -= r[pj]
    #print(r)
    ans = 0
    for pi,v in r.items():
        ans += v*(pi)
    ans %= MOD
    print(ans)
    
    

else:
    p = [1] + [i for i in divisor_list(n) if i%2==0 and i!=2]
    
    r = {pi:pow(k,(pi+1)//2,MOD) for pi in p}
    for pi in p:
        for pj in p:
            if pj >= pi: break
            if pi%pj==0:
                r[pi] -= r[pj]

    #print(r)
    ans = 0
    for pi,v in r.items():
        if pi==1:
            ans += v
        else:
            ans += v*(pi//2)
    ans %= MOD
        
        
    print(ans)

Submission status: Accepted

Solution code:
def prime_factor(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            while n % i == 0:
                n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors


def mebius(n):
    res = {}
    primes = prime_factor(n)
    m = len(primes)
    for i in range(1 << m):
        mu = 1
        d = 1
        for j in range(m):
            if i >> j & 1:
                mu *= -1
                d *= primes[j]
        res[d] = mu
    return res


mod = 10**9+7
N, K = map(int, input().split())
div = divisors(N)

ans = 0

for x in div:
    div2 = divisors(x)
    mu = mebius(x)
    cnt = 0
    for y in mu.keys():
        cnt += pow(K, ((x//y)+1)//2, mod)*mu[y]
    if x % 2 == 0:
        cnt *= pow(2, mod-2, mod)
    ans += x*cnt
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

MOD = 10**9 + 7

N,K = map(int,input().split())

U=int(10**4.5+10)
div = np.arange(1,U,dtype=np.int64)
div = div[N%div==0]
div = sorted(np.union1d(div,N//div))

A = {d:pow(K,int((d+1)//2),MOD) for d in div}
B = {}
for d in div:
    B[d] = A[d] - sum(B[dd] for dd in div if dd < d and d%dd == 0)

answer = sum(B[d] * (d//2 if d%2 == 0 else d) for d in div)
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = []; T = []
for x in range(1, int(N**.5)+1):
    if N % x == 0:
        S.append(x)
        if x*x < N:
            T.append(N//x)
T.reverse()
S += T
M = len(S)
U = []

MOD = 10**9 + 7
ans = 0
v = 0
for i in range(M):
    x = S[i]
    v = pow(K, (x+1)//2, MOD)
    for j in range(i):
        y = S[j]
        if x % y == 0:
            v -= U[j]
    U.append(v % MOD)
    ans = (ans + (v * x if x & 1 else v * (x//2))) % MOD
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
i = 1
M = N
div = []
while i * i <= N:
    if N % i == 0:
        div.append(i)
        if N // i != i:
            div.append(N // i)
    i += 1


div = sorted(div)
N1 = len(div)
num = [0] * (N1 + 1)
ans = 0
for i in range(N1):
    num[i] = pow(K, (div[i] + 1) // 2, MOD)
    for j in range(i):
        if div[i] % div[j] == 0:
            num[i] = num[i] - num[j] + MOD
            num[i] %= MOD

    if div[i] % 2 == 0:
        ans += div[i] * num[i] // 2
        ans %= MOD
    else:
        ans += div[i] * num[i]
        ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
M=10**9+7;D=[];i=1;r=0;N,K=map(int,input().split())
while i*i<=N:
	if N%i==0:D.append(i);i*i<N and D.append(N//i)
	i+=1
D.sort();N=[]
for i in range(len(D)):
	N.append(pow(K,-~D[i]//2,M))
	for j in range(i):
		if D[i]%D[j]==0:N[i]=(N[i]-N[j])%M
	r=(r+(N[i]*D[i]*pow(2,M-2+D[i]%2,M)))%M
print(r)

Submission status: Accepted

Solution code:
M=10**9+7;D=[];i=1;r=0;N,K=map(int,raw_input().split())
while i*i<=N:
	if N%i==0:D.append(i);i*i<N and D.append(N/i)
	i+=1
D.sort();N=[]
for i in range(len(D)):
	N.append(pow(K,-~D[i]/2,M))
	for j in range(i):
		if D[i]%D[j]==0:N[i]=(N[i]-N[j])%M
	r=(r+(N[i]*D[i]*pow(2,M-2+D[i]%2,M)))%M
print r

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

vector<bool> isp;

void sieve(int x=pow(10,6)+10) {
  isp.resize(x,true); 
  isp[0] = false;
  isp[1] = false;
  for (int i=2; pow(i,2)<=x; i++) {
    if (isp[i]) for(int j=2; i*j<=x; j++) isp[i*j] = false;
  }
}

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

ll pnk(ll n, ll k) {
  ll pn = n, now = 0, result = 1;
  while (k>=1ll<<now) {
    if (k&1ll<<now) result = result * pn % MOD;
    pn = pn * pn % MOD;
    now++;
  }
  return result;
}

int main() {
  ll N, K; cin >> N >> K;

  // map<string, ll> m;
  // rep(i,1<<N/2) {
  //   string S; rep(j,N/2) S += i&1<<j ? '1' : '0';
  //   rep(j,N/2) S += S[N/2-1-j];
  //   rep(j,N) {
  //     m[S]++;
  //     S = S.substr(1) + S[0];
  //   }
  // }
  // cout << m.size() << endl;

  sieve();
  vector<ll> yaku;
  for (ll i=1; i*i<=N; i++) {
    if (N%i==0) {
      yaku.push_back(i);
      if (i*i!=N) yaku.push_back(N/i);
    }
  }
  sort(all(yaku));
  // debug(all(yaku));

  ll l = yaku.size();
  vector<ll> count(l,0);

  rep(i,l) {
    count[i] = pnk(K,(yaku[i]+1)/2);
    rep(j,i) if (yaku[i]%yaku[j]==0) count[i] = (count[i]-count[j]+MOD) % MOD;
  }
  // debug(all(count));

  ll result = 0; rep(i,l) result = (result+(yaku[i]%2 ? yaku[i] : yaku[i]/2)*count[i]) % MOD;
  cout << result << endl;

  return 0;
}

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k = map(int,readline().split())
MOD = 10**9+7

if n&1:
    ans = k + (pow(k,(n+1)//2,MOD)-k)*n
    print(ans%MOD)

else:
    assert 0
    def divisor_list(N): #約数のリスト
        if N == 1: return [1]
        res = []
        for i in range(1,N):
            if i*i >= N: break
            if N%i == 0:
                res.append(i)
                res.append(N//i)
        if i*i == N: res.append(i)
        return sorted(res)

    p = [1] + [i for i in divisor_list(n) if i%2==0 and i!=2]
    
    r = {pi:pow(k,(pi+1)//2,MOD) for pi in p}
    for pi in p:
        for pj in p:
            if pj >= pi: break
            if pi%pj==0:
                r[pi] -= r[pj]

    #print(r)
    ans = 0
    for pi,v in r.items():
        if pi==1:
            ans += v
        else:
            ans += v*(pi//2)
    ans %= MOD
        
        
    print(ans)

Submission status: Runtime Error

Solution code:
@parallel
@roles('allgame')
def _last_redis_save():
	with cd(get_deploy_path()):
		redisSet = set()
		ret = run('supervisorctl status')
		for line in ret.split('\n'):
			line = line.strip()
			if line.find('RUNNING') >= 0 and line.find('redis') >= 0:
				name = line.split()[0].strip()
				redisSet.add(name)

		ret = []
		with cd('db'):
			for redis in sorted(list(redisSet)):
				port = redis[5:]
				ret.append(run('ls -l -h game%s.rdb' % port))
		return '\n'.join(ret)

def last_redis_save():
	result = execute(_last_redis_save)
	for k in sorted(result.keys()):
		print '-'*20
		print k, ':'
		v = result[k]
		print v