动态点分治
题目大意:
\(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;
- }
来源: http://www.bubuko.com/infodetail-2797996.html