1.1 题目描述

春宵和秋锅比赛现农。

春宵说：我的农气值有： 这么大，你是不可能比我大的。

秋锅笑而不语。他在后面加了一个： (mod M) 。

然后，他问春宵：你的农气值现在是多少呢？

（好冷的题目。。）

1.2 输入格式

一行 3 个数，依次为M,K,N 。

1.3 输出格式

一行 1 个数，表示春宵的农气值。

1.4 样例输入

98 3 4

1.5 样例输出

2

1.6 数据范围

对于 20%的数据：N,M,K ≤ 10^3

对于 40%的数据：N,M ≤ 10^3,K ≤ 10^18

对于 80%的数据：M ≤ 10^5,N,K ≤ 10^18

对于 100%的数据：0 < M ≤ 3 × 10^6,N,K ≤ 10^18

 

我们可以发现直接计算1~n的k次方的和是不现实的，这时发现m的取值范围较小，然后打表找规律发现m为t^kmod m的一个循环节。

于是我们只需用快速幂计算1~m的k次方取模的值就行了。

但是又不能对每一个数都做快速幂，我们可以发现合数的幂是由质数转来的，于是我们加上一个线性筛素数，只对素数做快速幂，在筛数的时候顺便转移t^kmod m的值。

1 program Neayo; 2 const 3         inf='sum.in'; 4         ouf='sum.out'; 5 var 6         i,j,tot:longint; 7         k,mo,n,ans,sum:int64; 8         q:array[0..250000]of longint; 9         a:array[0..3000000]of int64;10         p:array[0..3000000]of boolean;11 procedure init;12 begin13      assign(input,inf);assign(output,ouf);14      reset(input);rewrite(output);15      readln(mo,k,n);16      close(input);17 end;18 function quickpower(num:int64):int64;19 var tmp,time:int64;20 begin21      tmp:=1;time:=k;22      while time>0 do23      begin24           if (time and 1)=1 then tmp:=(tmp*num)mod mo;25           time:=time shr 1;26           if tmp mod mo=0 then exit(0);27           num:=(num * num)mod mo;28      end;29      exit(tmp mod mo);30 end;31 procedure go;32 begin33      a[1]:=1 mod mo;34      sum:=a[1];35      for i:=2 to mo do36      if i<=n then37      begin38           if not p[i] then39           begin40                inc(tot);41                q[tot]:=i;42                a[i]:=quickpower(i);43           end;44           for j:=1 to tot do45           begin46                if i*q[j]>mo then break;47                p[i*q[j]]:=true;48                a[i*q[j]]:=(a[i]*a[q[j]]) mod mo;49                if i mod q[j]=0 then break;50           end;51           sum:=(sum+a[i]) mod mo;52      end53      else break;54      sum:=(sum*(n div mo))mod mo;55      if n>mo then56      begin57           j:=n mod mo;58           for i:=1 to j do59           sum:=(sum+a[i])mod mo;60      end;61      writeln(sum mod mo);62 end;63 begin64      init;65      go;66      close(output);67 end.