//半年前做的,如今回顾一下,还是有所收货的,数的唯一分解,.简单题. #include<iostream> #include<cstring> using namespace std; int a[1000001];int p[1000000]; //用a来筛去m的唯一分解后的质因子及其倍数,流下就是与其互质的数. int main() { int m,k; while(cin>>m>>k) { memset(a,0,sizeof(a)); memset(

[欧拉函数] 在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目.此函数以其首名研究者欧拉命名,它又称为Euler’s totient function.φ函数.欧拉商数等. 例如φ(8)=4,因为1,3,5,7均和8互质. 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明. [证明]: 设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理,A*B和C可建立一一对应的关系.因此φ(n)的值使用算术基本定理便知, 若 n= ∏p^(α(下标p))p|

题目连接 /* 求所有小于N且与N不互质的数的和. 若:gcd(n,m)=1,那么gcd(n,n-m)=1; sum(n)=phi(n)*n/2; //sum(n)为小于n的所有与n互质的数的和 //phi(n)为小于n的所有与n互质的数的个数 */ #include<cmath> #include<cstdlib> #include<vector> #include<cstdio> #include<cstring> #include<i

[HDU4135]Co-prime 题意 给出三个整数N,A,B.问在区间[A,B]内,与N互质的数的个数.其中N<=10^9,A,B<=10^15. 分析 容斥定理的模板题.可以通过容斥定理求出[1,n]与x互质的数的个数.方法是先将x进行质因子分解,然后对于每个质因子pi,[1,n]内可以被pi整除的数目为n/pi.可以通过容斥定理解决逆命题,既[1,n]与x不互质的数目.n/p1+n/p2+n/p3-n/p1p2-n/p1p3-n/p2p3+n/p1p2p3.既奇数是加,偶数是减.具体的

题意: 给你一个T,是样例的个数,接下来是五个数l1,r1,l2,r2,k  前四个数代表两个区间(l1,r1),(l2,r2)这个题l1=1,l2=1; 取x1属于(1,r1),x2属于(1,r2): 求使得gcd(x1,x2)==k 的(x1,x2)的个数,特别的(1,2)和(2,1)只计算一次: 思路: 他让求gcd等于k的   我们可以让r1,r2都除以k相当于求               取x1属于(1,r1/k),x2属于(1,r2/k): 求使得gcd(x1,x2)==1 的(x

链接:https://www.nowcoder.com/acm/contest/144/J来源:牛客网 skywalkert, the new legend of Beihang University ACM-ICPC Team, retired this year leaving a group of newbies again. Rumor has it that he left a heritage when he left, and only the one who has at lea

7834:分成互质组 总时间限制:  1000ms 内存限制:  65536kB 描述 给定n个正整数,将它们分组,使得每组中任意两个数互质.至少要分成多少个组? 输入 第一行是一个正整数n.1 <= n <= 10. 第二行是n个不大于10000的正整数. 输出 一个正整数,即最少需要的组数. 样例输入 6 14 20 33 117 143 175 样例输出 3 来源 2008年第十三届“华罗庚金杯”少年数学邀请赛 决赛第5题 分析: 这道题其实可以用DFS 加上染色的感觉.对每个数据往上判

这题满满的黑科技orz 题意:给出L,要求求出最小的全部由8组成的数(eg: 8,88,888,8888,88888,.......),且这个数是L的倍数 sol:全部由8组成的数可以这样表示:((10^x)-1)*(8/9) 那么有m=((10^x)-1)*(8/9)=k*L,answer即满足条件的最小的x 性质1:若ax=by且a和b互质,那么说明a中没有任何b的质因子,b的质因子一定都在x里.所以x是b的倍数. 所以先想方设法在等式中构造两个互质的数以便化简.我们取p=8/gcd(8,L

题意:给你x%ci=bi(x未知),是否能确定x%k的值(k已知) ——数学相关知识: 首先:我们知道一些事情,对于k,假设有ci%k==0,那么一定能确定x%k的值,比如k=5和ci=20,知道x%20=y,那么ans=x%k=y%5; 介绍(互质版)中国剩余定理,假设已知m1,m2,mn,两两互质,且又知道x%m1,x%m2..x%mn分别等于多少 设M=m1*m2*m3..mn,那么x在模M的剩余系下只有唯一解(也就是知道了上面的模线性方程组,就可以求出x%M等于多少) ——此题解法 针对

分析:考虑对给定的出圈序列进行一次模拟,对于出圈的人我们显然可以由位置,编号等关系得到一个同余方程 一圈做下来我们就得到了n个同余方程 对每个方程用扩展欧几里得求解,最后找到最小可行解就是答案. 当然不要忘了判无解的情况. 有非常多选手似乎都是一眼标算然后写挂了,对此表示很遗憾,但是此题确实是比较容易写挂的... 注:中国剩余定理 解模线性方程组的时候 有两种情况 1:一种是模数是两辆互质的,这样的题可以用LRJ白书上的模板,俗称CRT1 2:模数存在不互质的,这样的需要用合并方程的做法,俗称C

Description There is a hill with n holes around. The holes are signed from 0 to n-1. A rabbit must hide in one of the holes. A wolf searches the rabbit in anticlockwise order. The first hole he get into is the one signed with 0. Then he will get into

C互质个数 Time Limit:1000MS  Memory Limit:65536K Total Submit:55 Accepted:27 Description 贝贝.妞妞和康康都长大了,如今,他们已届小学毕业,老师给贝贝出了一道强化计算的题目,让她做一大堆除法,以确定两个数之间是否有公共的因子,并且还要数清楚没有公因子的数对.可是,毕竟有些数太大了,量又太多了,即使她与妞妞和康康联手,也没有耐心在一个小时做完这种吃力的事情啊.虽然他们真的知道该怎么做,可是,他们的心早就飞到海边的沙滩上

Hello Kiki Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 247 Accepted Submission(s): 107   Problem Description One day I was shopping in the supermarket. There was a cashier counting coins serio

Sample Input 3 4 5 18 36 360 2147483647 Sample Output 1 1 2 3 6 48 1073741823 题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3937 题目大意:圆上有N个点把圆分成N等分,求隔同样的点能一笔画全然部点的方法: 思考:要一笔画出,那么(N.K)必然没有在

1439 互质对 题目来源: CodeForces 基准时间限制:2 秒 空间限制:131072 KB 分值: 160 难度:6级算法题 有n个数字,a[1],a[2],…,a[n].有一个集合,刚开始集合为空.然后有一种操作每次向集合中加入一个数字或者删除一个数字.每次操作给出一个下标x(1 ≤ x ≤ n),如果a[x]已经在集合中,那么就删除a[x],否则就加入a[x]. 问每次操作之后集合中互质的数字有多少对. 注意,集合中可以有重复的数字,两个数字不同当且仅当他们的下标不同. 比如a[

Co-prime 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4135 input The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 1015) and (1 <=

#6164. 「美团 CodeM 初赛 Round A」数列互质 思路 : 对这个题来言,莫队可以 n*根号n 离线处理出各个数出现个的次数 ,同时可以得到每个次数出现的次数 , 但是还要处理有多少 次数 与ki互质 .根据数列的性质,无论这个区间多长,最长也就是 1 - n这个区间 ,所能产生的 不同的次数 也就是 根号 n 种  例如 长度为28的 数列    1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 不同的次数 只有 7

X问题 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3921    Accepted Submission(s): 1253 Problem Description 求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod

http://acm.hdu.edu.cn/showproblem.php?pid=5072 求n个不同的数(<=1e5)中有多少组三元组(a, b, c)两两不互质或者两两互质. 逆向求解,把所有不符合的情况求出来用总的情况数减去即可: 先用容斥求出和a[i] 互质的个数num ,然后不符合条件的 就是 num*(n-1-num); 求法见http://blog.csdn.net/u012774187/article/details/40399567 #include <cstdio>

Hello Kiki Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description One day I was shopping in the supermarket. There was a cashier counting coins seriously when a little kid running and singing "门前大桥下游过一

X问题 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description 求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10).   Input 输入数据的第一行为一个正整数