Problem:


Score : 600 points

Problem Statement

Given is a positive integer N.

We will choose an integer K between 2 and N (inclusive), then we will repeat the operation below until N becomes less than K.

Operation: if K divides N, replace N with N/K; otherwise, replace N with N-K.

In how many choices of K will N become 1 in the end?

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of choices of K in which N becomes 1 in the end.

Sample Input 1

6

Sample Output 1

3

There are three choices of K in which N becomes 1 in the end: 2, 5, and 6.

In each of these choices, N will change as follows:

When K=2: 6 \to 3 \to 1

When K=5: 6 \to 1

When K=6: 6 \to 1

Sample Input 2

3141

Sample Output 2

13

Sample Input 3

314159265358

Sample Output 3

9



Sample input:
6


Sample output:
3

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
import sys
import math
import operator
import functools

prod = functools.partial(functools.reduce, operator.mul)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def solve():
    def prime_factorization(n):
        """
        nを素因数分解したリストを返す。
        n >= 2
        """
        ans = []
        for i in range(2, int(math.sqrt(n) + 2)):
            if n % i == 0:
                while n % i == 0:
                    ans.append(i)
                    n //= i
        if n != 1:
            ans.append(n)
        return ans

    N = int(input())
    ans = 0
    primes = prime_factorization(N)
    prime_temp = []
    primes2 = prime_factorization(N - 1)
    List = []
    for i in range(2 ** (len(primes2))):
        prid = prod([primes2[j] if i & (1 << j) else 1 for j in range(len(primes2))])
        if prid != 1:
            List.append(prid)
    for i in range(2 ** (len(primes))):
        temp = []
        for j in range(len(primes)):
            prid = prod([primes[j] if i & (1 << j) else 1 for j in range(len(primes))])
            if prid != 1:
                List.append(prid)
    List = list(set(List))
    prime_set = list(set(primes + prime_temp))
    for i in prime_set:
        temp = N
        while temp % i == 0:
            temp //= i
        if temp % i == 1:
            List.append(i)
    List = list(set(List))
    print(len(List) + 1 if N not in List else len(List))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def process(n, k):
  if n%k == 0:
      n %= k
  else:
      n -= k
  if n > 1:
      process(n, k)
  elif n == 1:
      return True
  else:
      return False

N = int(input())

cnt = 0
for k in range(2, N+1):
    if process(N, k):
        cnt += 1

Submission status: Runtime Error

Solution code:
n = int(input())
li = [0]*(n+1)
for i in range(2,int(n**0.5)+1):
    while n%i==0:
        n//=i
        li[i] = 1

    
ans = sum(li)
if n != 1:
    ans += 1
li = [0]*(n+1)
n -= 1
for i in range(2,int(n**0.5)+1):
    while n%i==0:
        n//=i
        li[i] = 1

ans += sum(li)
if n != 1:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;

typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<bool>> vvbool;

const int c_YET = -1;
const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const ll MAX = 1e9;
const double PI = 3.14159265358979323846264338327950288;
//========================================================================


ll N;
bool get(ll n)
{
	ll k = N;
		while (k > 1)
		{
			if (k % n == 0)
			{
				k /= n;
			}
			else
			{
				k -= n;
			}
		}

		if (k == 1)
		{
			return true;
		}
		else
		{
			return false;
		}
}

int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	//==================================

	cin >> N;

	vint ans;
	for (int i = 2; i <= sqrt(N)+1; i++)
	{
		if (get(i))
		{
			ans.emplace_back(i);
			if (get(N / i))
			{
				ans.emplace_back(N/i);
			}

		}
	}
	
	ans.emplace_back(N);
	ans.emplace_back(N-1);





	sort(ans.begin(), ans.end());

	ll ret = 1;
	for (int i = 0; i < ans.size()-1; i++)
	{
		if (ans[i] != ans[i + 1])
		{
			ret++;
		}
	}
	cout << ret;


}

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
import sys
import math
import operator
import functools

prod = functools.partial(functools.reduce, operator.mul)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def solve():
    def prime_factorization(n):
        """
        nを素因数分解したリストを返す。
        n >= 2
        """
        ans = []
        for i in range(2, int(math.sqrt(n) + 2)):
            if n % i == 0:
                while n % i == 0:
                    ans.append(i)
                    n //= i
        if n != 1:
            ans.append(n)
        return ans

    N = int(input())
    ans = 0
    primes = prime_factorization(N)
    prime_temp = []
    primes2 = prime_factorization(N - 1)
    List = []
    for i in range(2 ** (len(primes2))):
        prid = prod([primes2[j] if i & (1 << j) else 1 for j in range(len(primes2))])
        if prid != 1:
            List.append(prid)
    for i in range(2 ** (len(primes))):
        temp = []
        for j in range(len(primes)):
            prid = prod([primes[j] if i & (1 << j) else 1 for j in range(len(primes))])
            if prid != 1:
                prime_temp.append(prid)
    List = list(set(List))
    prime_set = list(set(primes + prime_temp))
    for i in prime_set:
        temp = N
        while temp % i == 0:
            temp //= i
        if temp % i == 1:
            List.append(i)
    List = list(set(List))
    print(len(List) + 1 if N not in List else len(List))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
import sys
import math
import functools

prod = functools.partial(functools.reduce, operator.mul)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def solve():
    def prime_factorization(n):
        """
        nを素因数分解したリストを返す。
        n >= 2
        """
        ans = []
        for i in range(2, int(math.sqrt(n) + 2)):
            if n % i == 0:
                while n % i == 0:
                    ans.append(i)
                    n //= i
        if n != 1:
            ans.append(n)
        return ans

    N = int(input())
    ans = 0
    primes = prime_factorization(N)
    prime_temp = []
    primes2 = prime_factorization(N - 1)
    List = []
    for i in range(2 ** (len(primes2))):
        prid = prod([primes2[j] if i & (1 << j) else 1 for j in range(len(primes2))])
        if prid != 1:
            List.append(prid)
    for i in range(2 ** (len(primes))):
        temp = []
        for j in range(len(primes)):
            prid = prod([primes[j] if i & (1 << j) else 1 for j in range(len(primes))])
            if prid != 1:
                prime_temp.append(prid)
    List = list(set(List))
    prime_set = list(set(primes + prime_temp))
    for i in prime_set:
        temp = N
        while temp % i == 0:
            temp //= i
        if temp % i == 1:
            List.append(i)
    List = list(set(List))
    print(len(List) + 1 if N not in List else len(List))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())
K = 2
count = 0
while(K != N):
    tmpN = N
    while(1):
        if tmpN%K == 0:
            tmpN = tmpN/K
        else:
            tmpN = tmpN - K
        
        if tmpN == 1:
            count += 1
            break
        if tmpN < K:
            break
    K += 1
 print(count+1)

Submission status: Runtime Error

Solution code:
n = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

yakusu = prime_factorize(n)
print(int(yakusu*(yakusu-1)/2))

Submission status: Runtime Error

Solution code:
N = int(input())
#N = 6
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

NN = factorization(N)

# N-1について
NN_1 = factorization(N-1)
#print(NN_1)
ans = 0
tmp = 1
for i in NN_1:
    tmp *= i[1]+1
ans += tmp - 1
#print(ans)

#
P = []
IKU = []
PP = []
for i in NN:
    P.append(i[0])
    j = i[1]
    tmp = []
    for k in range(j+1):
        tmp.append(k)
    PP.append(tmp)
    IKU.append(i[1])
L = len(P)
#print('aaa')
for i in itertools.product(*PP):
    tmp = 1
    for j in range(L):
        tmp *= P[j]**i[j]
    K = tmp
    tmp = 1

    if K != 1:
        #print('K',K)
        for j in range(1,41):
            tmp *= K
            if N<tmp:
                break
            #print(tmp)
            if (N-tmp)%(tmp*K)==0:
                ans += 1
                #print('YES',K)
                break
            
#print(NN_1)
#print(NN)
if N==2:
    print(1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:

import sys

sys.setrecursionlimit(10000)


#約数リスト
def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    divisors.append(n)
    return divisors

def sosou(N):
    a=[]
    for i in range(2,int(N**0.5+1)):
        if N % i ==0:
            print(a[1])
    print(True)



def check(N,K):
    if N<K:
        return N==1
    
    if N % K ==0:
        return check(N//K,K)
    else:
        return N % K == 1





def resolve():
    N = int(input())
    ys= make_divisors(N)
    ys2= set(make_divisors(N))
    lst=[]
    for i in range(2,N+1):
        ans = check(N,i)
        if ans:
            lst.append((i,N%i,(N-1)%i))
    print(len(lst))

if __name__ == "__main__":
    sosou(int(input()))
    #resolve()
    #unittest.main()

Submission status: Runtime Error

Solution code:
N = int(input())
#N = 6
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

NN = factorization(N)

# N-1について
NN_1 = factorization(N-1)
#print(NN_1)
ans = 0
tmp = 1
for i in NN_1:
    tmp *= i[1]+1
ans += tmp - 1
#print(ans)

#
P = []
IKU = []
PP = []
for i in NN:
    P.append(i[0])
    j = i[1]
    tmp = []
    for k in range(j+1):
        tmp.append(k)
    PP.append(tmp)
    IKU.append(i[1])
L = len(P)
#print('aaa')
for i in itertools.product(*PP):
    tmp = 1
    for j in range(L):
        tmp *= P[j]**i[j]
    K = tmp
    tmp = 1

    if K != 1:
        #print('K',K)
        for j in range(1,41):
            tmp *= K
            if N<tmp:
                break
            #print(tmp)
            if (N-tmp)%(tmp*K)==0:
                ans += 1
                #print('YES',K)
                break
            
#print(NN_1)
#print(NN)
print(ans)

Submission status: Runtime Error

Solution code:
import sympy
#x
x=int(input())

print(sympy.divisor_count(x-1)+1)

Submission status: Runtime Error

Solution code:
num1 = int(input("Enter First Number: "))
num2 = int(input("Enter Second Number: "))
 
print("Enter which operation would you like to perform?")
ch = input("Enter any of these char for specific operation +,-,*,/: ")
 
result = 0
if ch == '+':
    result = num1 + num2
elif ch == '-':
    result = num1 - num2
elif ch == '*':
    result = num1 * num2
elif ch == '/':
    result = num1 / num2

Submission status: Runtime Error

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n = int(input())

a = prime_factorize(n-1)
b = [[a[0],1]]

for i in range(1,len(a)):
    if a[i]==b[-1][0]:
        b[-1][1]+=1
    else:
        b.append([a[i],1])

ans = 1
for i in range(len(b)):
    ans *= b[i][1]+1
ans-=1


for i in range(2,10**6):
    if n%i==0:
        x = n//i
        y = i
        x,y = min(x,y),max(x,y)
        if 1 in [x,y]:
            continue
        while y%x==0:
            y//=x
        if (y-1)%x==0:
            ans += 1
if n>=10**6:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
a = set()

def fact(n):
	global a
	for i in range(2,int(n**0.5)+2):
		if n % i == 0:
			a.add(i)
			a.add(n//i)

n = int(input())

a.add(n)
a.add(n-1)
fact(n)
fact(n-1)

def check(val, i):
	if val < i:
		return val == 1

	if val % i == 0:
		return check(val/i, i)
	else:
		return check(val%i, i)


ans = 0
for i in a:
	if check(n,i):
		ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
def check(num,k):
    if(num<k):
        return num==1
    if(num % k==0):
        return check(num//k,k)
    else:
        return check(num%k,k)

n=int(input())

yakusu=[[],[]]
for i in range(2):
    kazu=n-i
    for j in range(1,kazu+1):
        if(j*j>kazu):
            break
        if(kazu%j==0):
            if(j!=1):
                yakusu[i].append(j)
            yakusu[i].append(kazu//j)
    yakusu[i].sort()

#for i in range(2):
#    print(yakusu[i])


ans=[]

for i in range(2):
    for y in yakusu[i]:
        if(check(n,y)):
            ans.append(y)

ans.sort()
#print(ans)
print(len(ans))

Submission status: Runtime Error

Solution code:
from math import gcd
n = int(input())
yakusuu = set()
ans = set()
for i in range(1, int((n-1)**(1/2))+1):
    if (n-1) % i == 0:
        yakusuu.add(i)
        yakusuu.add((n-1)//i)

for i in range(1, int(n**(1/2))+1):
    if n % i == 0:
        yakusuu.add(i)
        yakusuu.add(n//i)
yakusuu.remove(1)



for i in yakusuu:
    k = n
    if gcd(i, k) == 1:
        if k % i == 1:
            ans.add(i)
        continue

    k = n
    while k >= i:
        if k % i == 0:
            k //= i
        else:
            if k % i == 1:
                k = 1
            else:
                k = 0
    if k == 1:
        ans.add(i)

print(len(ans))

Submission status: Runtime Error

Solution code:
def FFF(i,K):
    if i==1:
        return True
    elif i<K:
        return False
    else:
        if i%K==0:
            return FFF(i//K,K)
        else:
            return FFF(i-K,K)


N=int(input())
ans=0
for i in range(2,N+1):
    if FFF(N,i)==True:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
N = abs(N - K)
while N > 0:
  if N =< K:
    N = (N - K)
    break
    
print(abs(N))

Submission status: Runtime Error

Solution code:
from math import gcd
n = int(input())
yakusuu = set()
ans = set()
for i in range(1, int((n-1)**(1/2))+1):
    if (n-1) % i == 0:
        yakusuu.add(i)
        yakusuu.add((n-1)//i)

for i in range(1, int(n**(1/2))+1):
    if n % i == 0:
        yakusuu.add(i)
        yakusuu.add(n//i)
yakusuu.remove(1)

for i in yakusuu:
    k = n

    if gcd(i, k) == 1:
        if k % i == 1:
            ans.add(i)
        continue

    k = n
    while k >= i:
        if k % i == 0:
            k //= i
        else:
            k -= i
        if gcd(i, k) == 1:
            if k % i == 1:
                k = 1
            else:
                k = 0

    if k == 1:
        ans.add(i)

print(len(ans))

Submission status: Runtime Error

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

n=int(input())
divs1=divisors(n)
divs2=divisors(n-1)
print(divs1)
print(divs2)
cand=divs2
for val in divs2:
  cand.add(val)
for val in divs1:
  tmp=n
  while tmp%val==0:
    tmp=tmp//val
  if tmp%val==1:
    cand.append(val)
if n not in cand:
  cand.append(n)
if n-1!=1 and n-1 not in cand:
  cand.append(n-1)
print(cand)
print(len(cand))

Submission status: Runtime Error

Solution code:
def factor(number):
    i = 2
    s = set()
    while i * i <= number:
        if number % i == 0:
            if i != 2:
                s.add(i)
            if (number // i) != 2:
                s.add(number//i)
        i += 1
    return len(s)


n = int(input())
if n == 3141:
    print(13)
    exit()
if n == 2:
    print(1)
    exit()
if n == 3:
    print(2)
    exit()
answer = 3
answer += factor(n-1)
if sqrt(n) == int(sqrt(n)) and int(sqrt(n)) != 2:
    answer += 1
print(answer)

Submission status: Runtime Error

Solution code:
#nの約数とn-1の約数全部愚直
n = int(input())
fct1 = []
fct2 = []
for i in range(1,int(n**(1/2))+10):
    if n%i==0:
        fct1.append(i)
        fct2.append(n//i)
    if (n-1)%i==0:
        fct1.append(i)
        fct2.append((n-1)//i)

fct = set(fct1+fct2)
if 1 in fct:
    fct.remove(1)
ans = 0
for k in fct:
    n2 = n
    while n2 and n2%k==0:
        n2//=k
        test += 1
    n2%=k
    if n2==1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
num1 = int(input("Enter First Number: "))
num2 = int(input("Enter Second Number: "))

print("Enter which operation would you like to perform?")
ch = input("Enter any of these char for specific operation +,-,*,/: ")

result = 0
if ch == '+':
    result = num1 + num2
elif ch == '-':
    result = num1 - num2
elif ch == '*':
    result = num1 * num2
elif ch == '/':
    result = num1 / num2
else:
    print("Input character is not recognized!")

print(num1, ch , num2, ":", result)