牛客网NOIP赛前集训营-提高组（第四场）游记
动态点分治
题目大意：
\(T(t\le10000)\)组询问，求\([l,r]\)中\(k(l,r,k<2^{63})\)的非负整数次幂的数的个数。
思路：
暴力，注意特判\(0\)和\(1\)的情况。
源代码：
#include<cstdio>
#include<cctype>
typedef unsigned long long uint64;
inline uint64 getint() {
register char ch;
while(!isdigit(ch=getchar()));
register uint64 x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
uint64 ans[64];
int main() {
for(register int T=getint();T;T--) {
const uint64 l=getint(),r=getint(),k=getint();
if(k==0) {
if(l>1) {
puts("None.");
continue;
}
if(l==0) printf("0 ");
if(r!=0) printf("1 ");
puts("");
continue;
}
if(k==1) {
puts(l<=1&&1<=r?"1":"None.");
continue;
}
uint64 pwr=1;
ans[0]=0;
for(register int i=0;i<63;i++) {
if(l<=pwr&&pwr<=r) {
ans[++ans[0]]=pwr;
}
if(pwr>1.*r/k) break;
pwr=pwr*k;
}
if(ans[0]==0) {
puts("None.");
} else {
for(register uint64 i=1;i<=ans[0];i++) {
printf("%llu%c",ans[i]," \n"[i==ans[0]]);
}
}
}
return 0;
}
区间：
题目大意：
给定一个长度为\(n(n\le4\times10^6)\)的数列\(A(A_i\le10^{18})\)，求一个最长的区间满足这个区间的\(\gcd\)本身也是这个区间的一个元素。
思路：
枚举每个数\(k\)作为区间\(\gcd\)，向左右扩展找到极大化区间\([l,r]\)，那么\([l,r]\)中其它元素都没有再枚举的必要。下一个\(k\)直接从\(r+1\)开始即可。
卡读入，直接getchar会被卡。使用mmap即可AC。
源代码：
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<sys/mman.h>
#include<sys/stat.h>
class MMapInput {
private:
char *buf,*p;
int size;
public:
MMapInput() {
register int fd=fileno(stdin);
struct stat sb;
fstat(fd,&sb);
size=sb.st_size;
buf=reinterpret_cast<char*>(mmap(0,size,PROT_READ,MAP_PRIVATE,fileno(stdin),0));
p=buf;
}
char getchar() {
return (p==buf+size||*p==EOF)?EOF:*p++;
}
};
MMapInput mmi;
typedef long long int64;
inline int64 getint() {
register char ch;
while(!isdigit(ch=mmi.getchar()));
register int64 x=ch^'0';
while(isdigit(ch=mmi.getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=4e6+1;
int64 a[N];
int main() {
const int n=getint();
for(register int i=1;i<=n;i++) a[i]=getint();
int ans=0;
for(int k=1;k<n;) {
int l=k,r=k;
for(;l>=1&&a[l]%a[k]==0;l--);
for(;r<=n&&a[r]%a[k]==0;r++);
ans=std::max(ans,r-l-1);
k=r;
}
printf("%d\n",ans);
return 0;
}
灭虫
同CF559E。