#P16745. 自然

自然

题目描述

在 unsigned long long 自然溢出的意义下,计算自然数幂和:

∑k=0n−1km(mod264).\sum_{k=0}^{n-1} k^m \pmod {2^{64}}.

换言之,你需要输出上述和对 2642^{64} 取模后的结果。

规定:

00=1.0^0=1.

输入格式

输入一行两个整数 m,nm,n,中间以空格分隔。

注意:先输入 mm,再输入 nn。

输出格式

输出一个非负整数,表示

∑0≤k<nkm mod 264.\sum_{0\le k<n} k^m \bmod 2^{64}.

数据范围

对于全部数据:

0≤m≤107,1≤n≤1018.0\le m\le 10^7, \qquad 1\le n\le 10^{18}.

本题各测试点等分,测试点分布如下:

测试点编号 mm nn
1∼21\sim2 =0=0 ≤1018\le 10^{18}
3∼43\sim4 =1=1
5∼65\sim6 =2=2
7∼87\sim8 =3=3
9∼109\sim10 =4=4
11∼1211\sim12 =5=5
13∼1413\sim14 =9=9
15∼1615\sim16 =16=16
17∼1817\sim18 =25=25
19∼2019\sim20 =64=64
21∼2221\sim22 =100=100
23∼2423\sim24 =1024=1024
25∼2625\sim26 =4096=4096
27∼2827\sim28 =104=10^4
29∼3029\sim30 =105=10^5 ≤108\le 10^8
31∼3231\sim32 ≤109\le 10^9
33∼3433\sim34 ≤1010\le 10^{10}
35∼3635\sim36 ≤1018\le 10^{18}
37∼3837\sim38 ≤16\le 16 =108=10^8
39∼4039\sim40 ≤32\le 32
41∼4241\sim42 ≤64\le 64
43∼4443\sim44 ≤104\le 10^4
45∼4645\sim46 ≤105\le 10^5
47∼4847\sim48 ≤16\le 16 =109=10^9
49∼5049\sim50 ≤32\le 32
51∼5251\sim52 ≤64\le 64
53∼5453\sim54 ≤16\le 16 =5×109=5\times10^9
55∼5655\sim56 ≤32\le 32
57∼5857\sim58 ≤64\le 64
59∼6059\sim60 ≤3000\le 3000 ≤3000\le 3000
61∼6261\sim62 ≤107\le 10^7
63∼6463\sim64 ≤106\le 10^6
65∼6665\sim66 ≤104\le 10^4 ≤5×106\le 5\times10^6
67∼6867\sim68 ≤107\le 10^7
69∼7069\sim70 ≤10\le 10 ≤108\le 10^8
71∼7271\sim72 ≤109\le 10^9
73∼7473\sim74 ≤1010\le 10^{10}
75∼7675\sim76 ≤1018\le 10^{18}
77∼7877\sim78 ≤103\le 10^3 ≤108\le 10^8
79∼8079\sim80 ≤109\le 10^9
81∼8281\sim82 ≤1010\le 10^{10}
83∼8483\sim84 ≤1018\le 10^{18}
85∼8685\sim86 ≤106\le 10^6 ≤108\le 10^8
87∼8887\sim88 ≤109\le 10^9
89∼9089\sim90 ≤1010\le 10^{10}
91∼9291\sim92 ≤1018\le 10^{18}
93∼9493\sim94 ≤107\le 10^7 ≤108\le 10^8
95∼9695\sim96 ≤109\le 10^9
97∼9897\sim98 ≤1010\le 10^{10}
99∼10099\sim100 ≤1018\le 10^{18}