一些前置知识： 1.扩展欧几里得算法：                                          ax+by=gcd(a,b) 方程一个可行的解（x1,y1）求法： int exgcd(int a,int b,int &x,int &y){if(!b){x=1,y=0; return a;}int d=exgcd(b,a%b,y,x);y-=a/b*x;ret

题目链接 青蛙的约会 这里可以推荐大家看看题解中的第一篇皎月半洒花大佬的题解 下面是我自己的一个小思路，写完后写代码就可以说不是一般轻松了， 再附上关于对最后一步负数如何转正数的一个理解，比如S/gcd和l/gcd来源的一个视角的解答，这本书挺好的，安利给大家！《数论概论》【美】约瑟夫 H.西尔弗曼写的 附上代码 #include<bits/stdc++.h>using nam

参考：exgcd详解 - zzt1208 - 博客园 (cnblogs.com) exgcd（扩展欧几里得算法），用来求形如 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)（ a , b a,b a,b 为常数）的方程的一组整数解。（如果不确定等号右边是不是gcd，可以先当做gcd，求出来之后验证，是的话就是解，不是的话就不是

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。 证明：设 a>b。 　　1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0； 　　2，ab!=0 时 　　设 ax1+by1=gcd(a,b); 　　bx2+(a mod b)y2=gcd(b,a mod b); 　　根

Input 输入含有多组数据，第一行一个正整数T，表示这个测试点内的数据组数。 接下来T行，每行有五个整数p，a，b，X1，t，表示一组数据。保证X1和t都是合法的页码。 注意：P一定为质数 Output 共T行，每行一个整数表示他最早读到第t页是哪一天。如果他永远不会读到第t页，输出-1。 Sample Input 3 7 1 1 3 3 7 2 2 2 0 7 2 2

欧几里得算法： 两个数x和y的最大公约数gcd(x,y)=gcd(y,x%y).这个就不解释了。 关于Exgcd： 用法： exgcd用于求解不定方程ax+by=c的一组解。准确的说，它是用来求解ax+by=gcd(a,b)，的x和y。 求解过程： 采用递归方式，我们对a,b不断的求解gcd过程，并从中推出x和y. 我们假设有ax+by=gcd(a,b). 令a=b,b=a%b,则

这个题目坑啊，查来查去，排查了好久，发现自己快速幂写错了。。。 这个题目有三个询问 1、 yz y z y^z mod m o d mod p p p2、xyxyxy ≡ z(mod z ( m o d z(mod p) p ) p) （求x） 3、 yx≡z(mod y x ≡ z ( m o d y^x ≡z(mod p) p ) p)（求x） 第一个用快速幂求

传送门 题解 随便推柿子 然后ex.. upd: 还是挂一点题解吧.. 你把第一第二个数对后面每个数的贡献推出来 发现对于第n个数 第一个数对他的贡献有 f(n−2) f ( n − 2 ) f(n-2)个 第二个数对他的贡献有 f(n−1) f ( n − 1 ) f(n-1)个 其中 f f <script type="math/tex" id="MathJax-E

Description 给出a,b,c,x1,x2,y1,y2，求满足ax+by+c=0，且x∈[x1,x2],y∈[y1,y2]的整数解有多少对？ Input 第一行包含7个整数，a,b,c,x1,x2,y1,y2，整数间用空格隔开。 a,b,c,x1,x2,y1,y2的绝对值不超过10^8。 Output 输出整数解有多少对？ Sample Input 1 1

文章目录 扩展欧几里得算法ExgcdExgcd算法内容Exgcd求解一组整数解Exgcd算法拓展Exgcd算法通解 线性同余方程线性同余方程的一组解线性同余方程的通解线性同余方程的最小正整数解 小结 扩展欧几里得算法Exgcd Exgcd算法内容 给定 a , b , c , d a,b,c,d a,b,c,d,求解 a x   + b y   =   g c d ( a ,