【数论】【扩展欧几里得】Codeforces 710D Two Arithmetic Progressions
2024-10-18 17:09:49
题目链接:
http://codeforces.com/problemset/problem/710/D
题目大意:
两个等差数列a1x+b1和a2x+b2,求L到R区间内重叠的点有几个。
0 < a1, a2 ≤ 2·109, - 2·109 ≤ b1, b2, L, R ≤ 2·109, L ≤ R).
题目思路:
【数论】【扩展欧几里得】
据题意可得同余方程组 x=b1(mod a1) 即 x=k1*a1+b1
x=b2(mod a2) x=k2*a2+b2
化简,k1*a1=k2*a2+(b2-b1) 即 a1= (b2-b1)(mod a2)
于是只要求一个同余方程即可。令a=a1,b=a2,c=b2-b1。
扩展欧几里得求解x,再把x改为在L~R区间内的第一个通解,计算数量即可(每次增加lcm(a1,a2)答案+1)。
//
//by coolxxx
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-8)
#define J 10
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#define N 20000004
using namespace std;
typedef long long LL;
int cas,cass;
int n,m,lll,ans;
LL a1,a2,b1,b2,l,r;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b){x=,y=;return a;}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
LL a,b,c,d,x,y,ny,lcm;
// for(scanf("%d",&cas);cas;cas--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
// while(~scanf("%s",s+1))
while(~scanf("%I64d",&a1))
{
cin>>b1>>a2>>b2>>l>>r;
l=max(l,b1);l=max(l,b2);
d=exgcd(a1,a2,x,y);
lcm=a1/d*a2;
if((b2-b1)%d!=)
{
puts("");
continue;
}
a=a1/d;b=a2/d;c=(b2-b1)/d;
d=exgcd(a,b,x,y);
x=a1*(x*c)+b1;
if(x>l)x=x-(x-l)/lcm*lcm;
else x=x+(l--x+lcm)/lcm*lcm;
if(x>r)puts("");
else printf("%I64d\n",(r-x+lcm)/lcm-(l--x+lcm)/lcm);
}
return ;
}
/*
// //
*/
最新文章
- nano编辑器使用教程
- CoInitialize浅析二
- [转]KendoUI系列:Grid
- python 字节与字符串转换
- 注解:【有连接表的】Hibernate单向N->;N关联
- 《DSP using MATLAB》示例Example4.2
- 用SQL打印乘法口诀表
- Android 开发 --Unable to resolve target &#39;android-19&#39;
- .net framework缓存遍历
- Android学习路线(二十)运用Fragment构建动态UI
- improper Advertising identifier [IDFA] Usage. Your app contains the Advertising Identifier [IDFA] AP
- html5 兼容参考文档 与 浏览器hack兼容参考文档
- 6.解决AXIOS的跨域问题
- java集合练习
- Struts2中validate数据校验的两种常用方法
- XE10 clientDataset 访问 DataSnap 服务端报错问题,锲而不舍找方法,终于解决了
- yk-随记
- flask 之request用法
- 202. Happy Number (INT)
- 【自动化测试】基于IntelliJ IDEA的Gradle和testNG
热门文章
- windows下jboss启动、配置、访问
- C# 各种集合
- 测测你适合从事Web前端开发吗
- ashx页面 “检测到有潜在危险的 Request.Form 值”的解决方法(控制单个处理程序不检测html标签)
- 灵活运用绑定变量---declare匿名块使用绑定变量
- redhat6.4 配置centos6 yum替换
- [转]mysql导出导入中文表解决方法
- Become a Windows Insider and Test New Windows 10 Features
- sencha touch中用来格式化日期的字符串参数
- extjs下拉框添加复选框