【Foreign】不等式 [数论]
2024-08-31 00:21:23
不等式
Time Limit: 10 Sec Memory Limit: 128 MB
Description
小z热衷于数学。
今天数学课的内容是解不等式:L<=S*x<=R 。小z心想这也太简单了,不禁陷入了深深的思考:假如已知L,R,S,M ,满足L<=(S*x) mod M<=R 的最小正整数x该怎么求呢?
Input
第一行包含一个整数T,表示数据组数,接下来是T行,每行为四个正整数M, S, L, R 。
Output
对于每组数据,输出满足要求的x值,若不存在,输出-1 。
Sample Input
1
5 4 2 3
Sample Output
2
HINT
30%的数据中保证有解并且答案小于等于10^6;
另外20%的数据中保证L=R;
100%的数据中T<=100,M, S, L, R<=10^9。
Solution
闷声放题解qwq。
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<bitset>
using namespace std;
typedef long long s64; const int ONE = ;
const int MOD = 1e9 + ; int T;
s64 M, S, L, R; int get()
{
int res=,Q=;char c;
while( (c=getchar())< || c> )
if(c=='-')Q=-;
res=c-;
while( (c=getchar())>= && c<= )
res=res*+c-;
return res*Q;
} s64 Dfs(s64 M, s64 S, s64 L, s64 R)
{
if(L > R || M < L) return -; S %= M;
int res = (L - )/S + ;
if(res * S <= R) return res; int l = (-R % S + S) % S, r = (-L % S + S) % S;
int y = Dfs(S, M, l , r); if(y == -) return -; int x = (R + M * y) / S;
if(L <= S * x - M * y) return x;
return -;
} int main()
{
T = get();
while(T--)
{
M = get(); S = get();
L = get(); R = get(); printf("%d\n", Dfs(M, S, L, min(R, M-)));
} }
最新文章
- jQuery 的选择器常用的元素查找方法
- LINQ 左右连接
- [转]Ubantu vmware tools 安装
- HDU1434(终于用优先队列a了一题。。。了解度+1)
- script引入js文件问题
- Hashtable和HashMap类的区别
- 基于线程池和连接池的Http请求
- Light OJ 1253 Misere Nim (尼姆博弈(2))
- C#中Attribute介绍
- AngularJs学习笔记--Guide教程系列文章索引
- stm32f107vc在IAR环境下,引用库函数的工程文件的配置方法
- 关于《Swift开发指南》背后的那些事
- HTML5要点(一)
- elasticsearch集群搭建实例
- 手动创建第一个OC程序
- 基于Socket通讯(C#)和WebSocket协议(net)编写的两种聊天功能(文末附源码下载地址)
- iTOP-4418开发板Android 5.1/4.4丨Linux + Qt5.7丨Ubuntu12.04系统
- rsync如何不指定密码文件
- 关于nginx安装、iptables设置和查看端口指令netstat/ss
- linux配置PS1
热门文章
- 访问方式由http改为https curl:(51)
- 【Linux】- CentOS 防火墙iptables和firewall
- opencv2.4.0版本不支持Mat的大小自动调整?
- [计算机网络] 互联网协议栈(TCP/IP参考模型)各层的主要功能及相应协议
- (一)Redis简介及安装
- 求熵 python 代码
- hadoop的第一个hello world程序(wordcount)
- 【原创】宿主机远程登录虚拟机(windows server 2003系统)
- POJ2774:Long Long Message——题解
- BZOJ4259:残缺的字符串——题解