上传用户：jgrznzbfsj资料价格：5财富值&&『』文档下载 ：『』&&『』所属分类：机构：南京师范大学数学与计算机科学学院基金：国家自然科学基金资助项目()分类号：O156.1文献出处：关 键 词 ：&&&权力声明：若本站收录的文献无意侵犯了您的著作版权，请点击。摘要：ERDO S等于1987年曾证明了对于正整数a，b，如果对所有素数p，a，b被p除所得余数分别为a(m od p)，b(m od p)，都有a(m od p)≤b(m od p)，则a=b。该文则研究对哪些正整数a，b，满足对所有素数p，恒有a(m od p)≤b(m od p)+1，对1≤a≤5，确定了所有的b。即当a=1时，b可取一切正整数；a=2时，b=2k，k=0，1，2，…；a=3时，b=2，3，4，9；a=4时，b=3，4；a=5时，b=4，5。Abstract：ERDO s is equal to 1987 have proved the positive integers a, B, if for all primes P, a, B are p except income remainder respectively for a (M od P), B (M od P), (M od P) & B (M od P) a, a = B. In this paper, the research of which are integers a, B, to meet the of all prime numbers P and the constant a (M od P) & B (M od P) + 1, 1 and less than or equal to less than or equal to 5 to determine the B in all. That is, when a=1, B desirable a b=2k, a=2, k=0, 1, 2,... A=3, b=2, 3, 4, 9; a=4, b=3, 4; a=5, b=4, 5.正文快照：在模意义下考虑问题,这是数论中常用方法之一.如著名的Cauchy-D avenport定理是考虑Zp中和集的基数的大小.近年来,不少学者研究数列在模素数p的剩余类中的分布性质.如ELSHOLTZ[1],GARAEV和KUEH[2],CH INEN和MURATA[3]等研究了a模p的乘法阶的分布性质.其他相关文献见[4~7].对分享到：相关文献|求(1^b + 2^b + ... + a^b)(mod p)的值 - 推酷
求(1^b + 2^b + ... + a^b)(mod p)的值
的值。其中
分析：当然这个题由于
不大，而且
不一定是素数，我们可以看出对于
是有循环节的，循环节的长度为
大，所以我们也可以进一步优化，把
降小，当然这个就是用欧拉函数降幂即可。如下公式：
注意后面的条件。当然
时，就直接计算就行了，此时
不大。那么本题就容易了，举个例子：
所以，在实现过程中，我们先算不足一个循环节的部分，那么每一个循环节部分的值在此基础上补全，然后加起来即可。可以看出时间复杂度为
#include &iostream&
#include &string.h&
#include &stdio.h&
#include &math.h&
int phi(int n)
int t = (int)sqrt(1.0*n);
for(int i=2; i&=t; i++)
if(n % i == 0)
rea = rea - rea /
while(n % i == 0) n /=
rea = rea - rea /
int quick_mod(int a,int b,int m)
int ans = 1;
ans = ans * a %
a = a * a %
int Solve(int a,int b,int c)
int ph = phi(c);
if(b &= ph) b = b % ph +
int rem = a %
int div = a /
int ans1 = 0;
for(int i=1; i&= i++)
ans1 += quick_mod(i,b,c);
int ans2 = ans1;
for(int i=rem+1; i&=c; i++)
ans2 += quick_mod(i,b,c);
ans1 = (ans1 + ans2 * (div % c) % c) %
return ans1;
int main()
int a,b,c;
while(cin&&a&&b&&c)
cout&&Solve(a,b,c)&&
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致资格赛 A题 - 简书
资格赛 A题
画图说话：
前缀积推导
分析：9937 为质数，费马小定理+逆元，除法变乘法，快速幂取余
公式推导：(b/a)mod p=& (ba的逆元)mod p
根据费马小定理，a^(p-1) =1 mod p &=& a^(p-2) a= 1 mod p &=& a的逆元为 a^(p-2),所以(b/a)mod p &=&(b*a^(p-2)) mod p
用到的板子：快速幂取余、前缀积
快速幂取余
// x是底数，n是幂数，mod是取余数
LL mod_pow(LL x,LL n,LL mod)
LL res = 1;
while(n&0)
res = res * x %
x = x * x %
for(int i = 1 ;i&=i++)
H[i]=H[i-1]*(Hstr[i-1]-28)%
#include &cstdio&
#include &cstring&
#include &algorithm&
const int MAXN = 1e5 + 5;
int H[MAXN];
char Hstr[MAXN];
int N,l,r;
const int mods = 9973;
typedef long long LL;
//快速幂取余
LL mod_pow(LL x,LL n,LL mod)
LL res = 1;
while(n&0)
res = res * x %
x = x * x %
int main ()
while(scanf("%d",&N)!=EOF)
scanf("%s",Hstr);
int len =strlen(Hstr);
for(int i = 1 ;i&=i++)
H[i]=H[i-1]*(Hstr[i-1]*28)%
while(N--)
scanf("%d%d",&l,&r);
swap(l,r);
printf("%I64D\n",(LL)H[r]*mod_pow(H[l-1],mods-2,mods)%mods);
我已委托“维权骑士”（）为我的文章进行维权行动}