自然 - 题目详情 - https://new.bzoj.org:88

ID: 15955

传统题

2000ms

512MiB

难度: 9

上传者:

标签>

CF2600

数学

数论

组合数学

模运算

题目描述

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

\sum_{k=0}^{n-1} k^m \pmod {2^{64}}.

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

规定：

0^0=1.

输入格式

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

注意：先输入 $m$ ，再输入 $n$ 。

输出格式

输出一个非负整数，表示

\sum_{0\le k<n} k^m \bmod 2^{64}.

数据范围

对于全部数据：

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

本题各测试点等分，测试点分布如下：

测试点编号	$m$	$n$
$1\sim2$	$=0$	$\le 10^{18}$
$3\sim4$	$=1$
$5\sim6$	$=2$
$7\sim8$	$=3$
$9\sim10$	$=4$
$11\sim12$	$=5$
$13\sim14$	$=9$
$15\sim16$	$=16$
$17\sim18$	$=25$
$19\sim20$	$=64$
$21\sim22$	$=100$
$23\sim24$	$=1024$
$25\sim26$	$=4096$
$27\sim28$	$=10^4$
$29\sim30$	$=10^5$	$\le 10^8$
$31\sim32$		$\le 10^9$
$33\sim34$		$\le 10^{10}$
$35\sim36$		$\le 10^{18}$
$37\sim38$	$\le 16$	$=10^8$
$39\sim40$	$\le 32$
$41\sim42$	$\le 64$
$43\sim44$	$\le 10^4$
$45\sim46$	$\le 10^5$
$47\sim48$	$\le 16$	$=10^9$
$49\sim50$	$\le 32$
$51\sim52$	$\le 64$
$53\sim54$	$\le 16$	$=5\times10^9$
$55\sim56$	$\le 32$
$57\sim58$	$\le 64$
$59\sim60$	$\le 3000$	$\le 3000$
$61\sim62$	$\le 10^7$	$\le 3000$
$63\sim64$	$\le 10^7$	$\le 10^6$
$65\sim66$	$\le 10^4$	$\le 5\times10^6$
$67\sim68$	$\le 10^7$	$\le 5\times10^6$
$69\sim70$	$\le 10$	$\le 10^8$
$71\sim72$		$\le 10^9$
$73\sim74$		$\le 10^{10}$
$75\sim76$		$\le 10^{18}$
$77\sim78$	$\le 10^3$	$\le 10^8$
$79\sim80$		$\le 10^9$
$81\sim82$		$\le 10^{10}$
$83\sim84$		$\le 10^{18}$
$85\sim86$	$\le 10^6$	$\le 10^8$
$87\sim88$		$\le 10^9$
$89\sim90$		$\le 10^{10}$
$91\sim92$		$\le 10^{18}$
$93\sim94$	$\le 10^7$	$\le 10^8$
$95\sim96$		$\le 10^9$
$97\sim98$		$\le 10^{10}$
$99\sim100$		$\le 10^{18}$