题目链接 题意：问ax+by=1的一组x>0的解，如果无解输出sorry. 思路：根据裴蜀定理， ax+by=1有解当且gcd(a,b)=1。 然后根据扩展欧几里得算法，我们可以得到一组x,y。需要注意的是，这只是其中一组解。 x,y的通解为：**(x+kgx , y-kgy ） 其中：gx= b/gcd(a,b),gy = a/gcd(a,b),k为任意整数 ** /* *********************************************** Author :111qqz Created Time :Wed 12 Oct 2016 07:30:20 PM CST File Name …

前置技能点： 维基百科_裴蜀定理（贝祖等式） 对任何[整数](https://zh.wikipedia.org/wiki/) ，  和它们的[最大公约 …

先放资料。 前置技能点： 剩余系 剩余系**:设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]****，** 这m个数**{0,1,2,****…****m-1}**称为一个完全剩余系， 每个数称为相应类的代表元。 当m=10（偶数）时候，则{0,1,2,3,4,5,6,7,8,9}是最小非负完全剩余系 {-5,-4,-3,-2,-1,0,1,2,3,4,5} 是绝对值最小完全剩余系 {-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小 {1,2,3,4,5,6,7,8,9,10}是最小正完全剩余系 简化剩余系:在每个剩余类选取至1个与m …

题目链接 题意：一段数字串，如果一个数字k满足，将该串分成若干个长度为K的子串，这些子串两两满足每个字符出现的次数一样多，那么称为k是一个阿贝尔周期。现在问所有合法的阿贝尔周期。 思路： * 首先我们发现，所有的阿贝尔周期一定是数字串长度（设为n)的因数。 * 然后我们还发现。。。如果某个因子是阿贝尔周期，那么该因子的整数倍中恰好也是n的因子的也一定是阿贝尔周期，类似筛法。 * 然后我们还发现。。。最小的阿贝尔周期一定比数字串中的元素个数大。。。 然而其实后面两个不管也可以过吧。。。因为有点忘了n的约数个数的上界了。。。。 还是太保守了。。。 不过hack了四发哈哈哈。。。要是大号的话今天就紫了呜呜呜 /* …

题目链接 题意：给出n个数,q个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数9+7的答案是多少。 思路：这道题需要一点欧拉函数的知识。 phi(n)是欧拉函数，意义为小于等于n并且与n互质的数的个数。 To calculate the answer on every query let's use the formula , where _p_1, p_2, ..., p__k — all prime numbers which divided_n. 如果知道欧拉函数的这个公式。。。那么这道题就成了水题。。。。 考虑两个数a,b的欧拉函数。 一开始考虑也许有什么性质。。。查了下欧拉函数的wiki 欧拉函数_维基百科 欧拉函数 …

1053: [HAOI2007]反素数ant Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2750 Solved: 1559 [Submit][Status][Discuss] Description 　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x ，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么 ？ Input 　一个数N（1<=N<=2,000,000,000）。 Output 　不超过N的最大的反质数。 …

题目链接 题意：求约数个数恰好为n个的最小的x 思路：这道题是作为反素数的例题出现在acdreamer的博客里的。 但是实际上，这道题应该和反素数没有关系。 如果题目问的是最小的约数个数大于等于n的x，那么答案一定是反素数...打表就行了。。。 但是问的是**恰好，**比如如果n为5，那么最小的x是16，但是x不是反素数。 所以其实就是个dfs啦。 理论依据是： 一个数 A 可以分解成 p1k1 * p2k2 * …… * pnkn 其中p为素数。这样分解之后，A的因子个数 S = （k1+1） *（ k2+1） * …… *（ kn+1） 以及要找的是一个最小的x，满足约数个数等于n。 那么关于反素数的两个性质依然是满足的： …

题目链接 题意：求区间[a,b]中约数最多的那个数，如果有多个，输出最小的。 思路：看起来好像和反素数没什么关系...只是打个约数个数的表... 但是实际上，所有的答案恰好都是反素数。。。 我们回顾反素数的定义：设f(x)为x的约数个数，那么如果f(n)>f(i) (0<i<n),n就被称为反素数. 换句话说，对于所有f(x)==k的x组成的集合，最小的那个x就是反素数。 需要注意的是，因数个数并不单调。。因此上面那句话并不准确。。。 举个例子，16虽然有5个因子，是第一个有5个因子的数，但是16不是反素数，因为比16小的12有6个因子。 那么这个东西有什么用呢。。。。 我们发现。。。反素数的分布很稀疏。。。因 …

acdreamer的博客 wiki上的反素数是什么鬼orz...完全不是一个东西吧。。。。 反素数直观得理解。。。就是一个约数特别多的数。。。因为素数的约数最少。。。所以约数多的数就叫反素数（？随便口胡的... 由于1E18之前的反素数大概只有167个。。。所以打表可以很方便。。。 反素数是第一个约数“增长”到某个数的数，必须是“增长”，而不是第一个约数个数为某个数的数。 因为16是第一个约数个数为5的个数，但是16不是反素数，因为比16小的12有6的约数。。。 反素数的两个性质非常好用。。。 一个是反素数分解的质因子一定是连续的。。。 另一个是反素数分解的质因子的指数一定不增。。。 这两个性质都很显然。。。。证明没啥必要。。。 这 …

题目链接 题意：给出n个数，m个查询，每组查询一个区间[l,r]，问[l,r]中会被吃掉多少个（区间[l,r]中的数只有当其是其他所有数的因数时才不会被吃掉,顺便问一句。。a divide b 是 a除b,也就是b除以a,b/a的意思嘛23333） 思路：我们知道，不会被吃掉的数其实就是区间[l,r]中所有数的gcd,求gcd可以很容易用线段树办到。。。关键是还要统计该区间中等于gcd的数有多少个。 并不会做。 大概有两种做法。。。？ 一种是基哥@clq11111说的，将询问离线，然后从小到大排序插入，询问区间中等于x转化成询问区间中小于等于x的，和询问区间中小于等于x-1的，做差即为所求。 第二种办法是题解的讨论区部分的： 想了 …