[BZOJ 4921][Lydsy1706月赛]互质序列
2024-09-27 07:02:30
因为区间 gcd 的变换不会超过 log 个,所以我们可以暴力枚举区间起点,复杂度是 n*logn 的
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a;i<=b;++i) #define fd(i,a,b) for(int i=a;i>=b;--i) ,mod=; template <typename T> bool check_Max(T &x, const T&y) {return x<y?x=y,false:true;} template <typename T> bool check_Min(T &x, const T&y) {return x>y?x=y,false:true;} inline int gi() { ; char o; bool f=true; for(;!isdigit(o=getchar());) if(o=='-') f=false; )+(x<<)+(o&); ; } template <typename T> inline void Md(T &x) {if(x>=mod) x-=mod;} int gcd(int x,int y) { return x?gcd(y%x,x):y;} int gd1[maxn],gd2[maxn],nt[maxn],a[maxn],n,ans; int main() { #ifndef ONLINE_JUDGE freopen("10.in","r",stdin); #endif n=gi(); rep(i,,n) gd1[i]=gd2[i]=a[i]=gi(); rep(i,,n) gd1[i]=gcd(gd1[i-],gd1[i]); fd(i,n-,) gd2[i]=gcd(gd2[i+],gd2[i]); rep(i,,n) nt[i]=gd2[i]==gd2[i-]?nt[i-]:i-; rep(i,,n) { ]; ) Md(ans+=pos%mod); int L=n; while(L>i) { ,nt[L]+); pos=gcd(pos,gd2[R]); // printf("i=%d L=%d R=%d pos=%d--\n",i,L,R,pos);//de bug Md(ans+=1LL*pos*(L-R+)%mod); L=R-; } } ,R,pos=gd2[L]; ) { R=max(,nt[L]+),pos=gd2[R]; // peintf("L=%d R=%d pos=%d\n",L,R,pos); //de bug Md(ans+=1LL*pos*(L-R+)%mod); L=R-; } printf("%d\n",ans); ; }
今天的水题计划就到这里了,顺带提一句,今天S8世界总决赛 小组赛IG vs GRX时Stitch 的反向Q,连皮肤都和当年韦神的一样
放个图感受一下
最新文章
- java安全沙箱(一)之ClassLoader双亲委派机制
- Java 中的 static 使用之静态方法
- bitmapData
- ActiveX控件的Events事件
- HDU 3157 Crazy Circuits(有源汇上下界最小流)
- C#编译器怎么检查代码是否会执行
- 【转】VirtualBox下Ubuntu共享文件
- java_method_readFile读取文件文本txt
- python 单元测试
- php中如何给类规范的注释
- 19 子线程刷新UI runOnUiThread
- (二)jdk8学习心得之Lambda表达式
- 后台管理系统之邮件开发(Java实现)
- POJ 3667 Hotel(算竞进阶习题)
- Qt ------ 添加某个功能,比如(QSerialPort)注意事项
- CentOS7+Nginx配置Tomcat负载均衡环境
- [Windows Azure] How to Deploy a Database to Windows Azure
- 第五课 JAVA反射获取对象属性和方法
- Confluence 6 从 Crowd 或 JIRA 应用中切换回使用内部用户管理
- BZOJ 4443: [Scoi2015]小凸玩矩阵 最大流