字典树（11）
题目来源：&
基准时间限制：1.5&秒 空间限制：262144&KB 分值:&160&
给出一个长度为N的正整数数组A，再给出Q个查询，每个查询包括3个数，L, R, X (L &= R)。求A[L] 至 A[R] 这R - L + 1个数中，与X 进行异或运算(Xor)，得到的最大值是多少？
第1行：2个数N,&Q中间用空格分隔，分别表示数组的长度及查询的数量(1&&=&N&&=&50000,&1&&=&Q&&=&50000)。
第2&-&N+1行：每行1个数，对应数组A的元素(0&&=&A[i]&&=&10^9)。
第N+2&-&N+Q+1行：每行3个数X,&L,&R，中间用空格分隔。（0&&=&X&&=&10^9，0&&=&L&&=&R&&&N)
输出共Q行，对应数组A的区间[L,R]中的数与X进行异或运算，所能得到的最大值。
Output示例
本来以为会超时，没想到竟然水过去了
#include&iostream&
#include&algorithm&
#include&cstdio&
#include&cstdlib&
#include&cstring&
#include&vector&
#include&map&
#include &bits/stdc++.h&
const int N = 50000+10;
typedef long long LL;
typedef pair&int,int&
vector&int&p[N*30];
int rt[N*30][2],
void insert1(LL x,int id)
int root=0;
for(int i=30;i&=0;i--)
int v=((x&(1&&i))?1:0);
if(rt[root][v]==-1)
rt[root][v]=
rt[cnt][0]=rt[cnt][1]=-1;
root=rt[root][v];
p[root].push_back(id);
void get(LL x,int l,int r)
int root=0;
for(int i=30;i&=0;i--)
int v=((x&(1&&i))?1:0);
if(rt[root][1^v]!=-1)
int y=rt[root][1^v];
int pos=lower_bound(p[y].begin(),p[y].end(),l)-p[y].begin();
if(pos!=p[y].size()&&p[y][pos]&=l&&p[y][pos]&=r)
ans|=(1&&i);
if(rt[root][v]!=-1)
int y=rt[root][v];
if(v==1) ans^=(1&&i);
int main()
scanf(&%d %d&, &n, &m);
rt[0][0]=rt[0][1]=-1;
for(int i=0;i&n;i++)
scanf(&%lld&, &x);
insert1(x,i);
while(m--)
scanf(&%lld %d %d&, &x, &l, &r);
get(x, l, r);
printf(&%lld\n&,ans);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
(8)(78)(30)(2)(21)(43)(28)(7)(73)(79)(53)(10)(53)HDU 3358 Period of an Infinite Binary Expansion 推荐！！（欧拉函数，费马小定理） - java开发指南博客 【转载】 - ITeye博客
转载请注明出处，谢谢
by---cxlove
将一个分数化成小数，转化成二进制后寻找循环节
对于分数P/Q而言，首先化成最简，调整为P'=P/GCD(P,Q) Q'=Q/GCD(P,Q)
我们知道转化成二进制，其实就是不断乘2，如果大于1，则去掉1，当前位为1，否则为0.
表示成分数的时候便是P/Q,2*P/Q如果分子大于分母，则减掉，也相当于取余。
于是我们假设在第I位的时候开始循环，第J位出现重复。
而出现循环反正在分数上便是分母和分子都相同，由于在这里分母是不变的，只考虑分子
那么（P'*2^I）%Q'==(P'*2^J)%Q ;
一个同余式，作 些调整 P'*(2^J-2^I)==0(MOD Q')
P'*2^I*(2^(J-I)-1)==0(MOD Q')
变成P'*2^I*(2^(J-I)-1)|Q’
其中P'与Q'互质。那么2^I*(2^(J-I)-1)|Q’
而(2^(J-I)-1是奇数，那么I的值便是Q'里面有多少个2^的幂，第一部分已经解决
假设Q'除掉2的幂之后为Q''
那么Q''|(2^(J-I)-1)，由费马小定理或者欧拉定理可知
若A与P互质，则A^PHI(P) == 1 (MOD P)
所以2^X ==1 (mod Q'')必定存在解。
我们要求的是最小的解，则枚举PHI(Q'')的因子，从小开始判断
2^X==1(MOD Q'')
#include&iostream&
#include&cstdio&
#include&cstring&
#include&algorithm&
#include&cmath&
#define LL long long
#define N 1000000
LL gcd(LL a,LL b){
return b==0?a:gcd(b,a%b);
LL get_eular(LL n){
for(LL i=2;i*i&=n;i++)
if(n%i==0){
while(n%i==0){
LL PowMod(LL a,LL b,LL MOD){
ret=(ret*a)%MOD;
a=(a*a)%MOD;
LL fact[100000],
void get_fact(LL n){
for(LL i=2;i*i&=n;i++)
if(n%i==0){
fact[cnt++]=i;
fact[cnt++]=n/i;
int main(){
int cas=0;
while(scanf("%lld/%lld",&p,&q)!=EOF){
LL t=gcd(p,q);
while(!(q&1)){
LL phi=get_eular(q),
get_fact(phi);
fact[cnt++]=
sort(fact,fact+cnt);
for(int i=0;i&i++)
if(PowMod(2,fact[i],q)==1){
ans=fact[i];
printf("Case #%d: %d,%lld\n",++cas,c,ans);
浏览: 5436627 次
写的这么详细，全面，对架构师的工作职责，个人能力都进行了梳理。 ...
/docs/ ...
/docs/ ...
不错的界面控件知识，感谢分享！扫二维码下载作业帮
2亿+学生的选择
下载作业帮安装包
扫二维码下载作业帮
2亿+学生的选择
己知a=18,m=77,求使a^x≡1(mod m)成立的最小自然数x用费马小定理和欧拉定理的知识求解,急.收到请速回复谢谢
本吧wan849
扫二维码下载作业帮
2亿+学生的选择
欧拉定理(a,m)=1,则a^φ(m)≡1 (mod m)我们可以把77分成7×11来考虑,即找使18^y≡1(mod 7)和18^z≡1(mod 11)的最小自然数y和z.由欧拉定理可得18^6≡1 (mod 7) 和18^10≡1 (mod 11)18≡4(mod 7),则4^6≡1(mod 7),6=2×3,易验证4^3≡1(mod 7),则18^3≡1(mod 7)y最小为3.18≡7(mod 11),则7^10≡(mod 7),10=2×5,易验证7^2和7^5模11均不为1,所以z最小为10.综合两者,3和10的最小公倍数为30,所以最小的x为30.18^30≡1(mod 77)
则4^6≡1(mod 7)怎么来的，能说清楚些吗?我看不明白，急，收到请速回复谢谢！
4和7互素，由欧拉定理可得4^φ(7)≡1 (mod 7)
由于7为素数所以φ(7)=6.
后面我有地方打错了，是：
”18≡7(mod 11)，则7^10≡1(mod 11)，10=2×5，易验证7^2和7^5模11均不为1“
这里也是欧拉定理φ(11)=10
其他类似问题
扫描下载二维码扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
用同余理论知识求解,急收到请回复谢谢求54^1347除以17的非负最小余数
格子控shy317
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
要用到的知识点：费马小定理.（费马小定理是数论中的一个重要定理,其内容为：假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1（mod p） 假如p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1）用在该题中就是54^(17-1)≡1(mod 17),也就是54^16≡1(mod 17),而+3,所以54^1347≡(54^16)^84*54^3≡54^3≡9（mod 17）所以答案是9.
其他类似问题
扫描下载二维码}