Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Alternating Sum of Digits
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 206Accepted: 41

Description

Any integer number can be written as a sequence of digits in a specific system of base. For example, 5 in decimal based system can be written as 101 in binary based system. By writting down every number from 1 to N in system of base K one by one, we obtain a long sequence of digits. Your task is to calculate the alternating sum of digits, i.e. the difference between the sum of digits with odd index in the sequence and the sum of ones with even index.

For example, the sequence is 11011100101 and the alternating sum is 1 (the result of +1-1+0-1+1-1+0-0+1-0+1) given K = 2 and N = 101.

Input

K (1 < K ≤ 10) and N ( ≤ 1020, in the system of base K)

Output

The alternating sum. You should print it in decimal based system.

Sample Input

2 101

Sample Output

1

Hint

It is safe to use 64-bit signed integral arithmetic.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator