【NOIP训练】【规律+数论】欧拉函数的应用
Problem1【题目大意】给出多组数据，给出 求出。题解证明: 除了以为均为偶数，所以互质的个数成对。由得。所以对于每对的和为，共有对。则Problem2【题目大意】在第一个圆上写入 ，在第二个圆上写入，此后每一次在前一个圆的基础上，每两个数之间写上他们的和，定义为第i个圆中数字i的个数。给出，求...
【BZOJ-4173】数学 欧拉函数 + 关于余数的变换
4173:数学TimeLimit: 10Sec MemoryLimit: 256MBSubmit: 306 Solved: 163[Submit][Status][Discuss]DescriptionInput输入文件的第一行输入两个正整数。Output如题SampleInput56Sampl...
hdu 3307 Description has only two Sentences (欧拉函数+快速幂)
DescriptionhasonlytwoSentencesTimeLimit:3000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):852AcceptedSubmission(s):259Pr...
【bzoj2401】陶陶的难题I “高精度”+欧拉函数+线性筛
题目描述求输入第一行包含一个正整数T，表示有T组测试数据。接下来T<=10^5行，每行给出一个正整数N,N<=10^6。输出包含T行，依次给出对应的答案。样例输入71101001000100001000001000000样例输出121271844622418301130466018271...
lightoj1370欧拉函数/素数筛
这题有两种解法，1是根据欧拉函数性质：素数的欧拉函数值=素数-1（可根据欧拉定义看出）欧拉函数定义：小于x且与x互质的数的个数#include<map>#include<set>#include<cmath>#include<queue>#includ...
uva10820（欧拉函数，排列组合）
/*translation:给定一个数n，任意两个元素组成的二元组（x,y）.其中xy均小于n。任意两个二元组之间定不存在(k*xi,k*yi)=(xj,yj);问这样的二元组有多少个。solution:排列组合，欧拉函数满足条件的二元组的两个元素之间肯定互素，如果两个元素不互素，肯定存在一个整数k...
POJ 2478 Farey Sequence（欧拉函数前n项和）
A- FareySequenceTimeLimit:1000MS MemoryLimit:65536KB 64bitIOFormat:%I64d&%I64uSubmit Status Practice POJ2478DescriptionTheFareySequenceFnf...
ACM数论之旅7---欧拉函数的证明及代码实现（我会证明都是骗人的╮(￣▽￣)╭）
欧拉函数，用φ(n)表示欧拉函数是求小于等于n的数中与n互质的数的数目辣么，怎么求哩？~(～o￣▽￣)～o可以先在1到n-1中找到与n不互质的数，然后把他们减掉比如φ(12)把12质因数分解，12=2*2*3，其实就是得到了2和3两个质因数然后把2的倍数和3的倍数都删掉2的倍数：2,4,6,8,10...
BZOJ 2818 GCD 【欧拉函数 || 莫比乌斯反演】
传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=28182818:GcdTimeLimit: 10Sec MemoryLimit: 256MBSubmit: 9236 Solved: 4126[Submit][Status][Discus...
Bi-shoe and Phi-shoe（欧拉函数/素筛）题解
Bi-shoeandPhi-shoeBambooPole-vaultisamassivelypopularsportinXzhiland.AndMasterPhi-shoeisaverypopularcoachforhissuccess.Heneedssomebamboosforhisstudent...
计数与概率基础（容斥、有重复元素的全部排列、可重复选择的全排列、杨辉、二项式定理、欧拉函数）
1、容斥原理。如果班里有15个人喜欢物理，10个人喜欢英语，16个人喜欢数学，那么班里面有多少个人呢？10+16+15显然是错的，因为存在一个人既喜欢物理也喜欢英语，那么就把这些重复加的人的数量给剪掉。也就是减去既喜欢物理又喜欢英语的人，既喜欢英语又喜欢数学的人，既喜欢数学又喜欢物理的人，这样就把刚...
【bzoj2190】【仪仗队】欧拉函数+线性筛（浅尝ACM-J）
向大（hei）佬（e）*学（di）习（tou）Description作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N*N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。现在，C君希望你告诉他队伍整齐时能看到的...
BZOJ4804 欧拉心算（莫比乌斯反演+欧拉函数+线性筛）
一通套路后得Σφ(d)μ(D/d)⌊n/D⌋2。显然整除分块，问题在于怎么快速计算φ和μ的狄利克雷卷积。积性函数的卷积还是积性函数，那么线性筛即可。因为μ(pc)=0(c>=2)，所以f(pc)还是比较好算的，讨论一波即可。#include<iostream>#include<...
FZU 1759 欧拉函数 降幂公式
Description GivenA,B,C,YoushouldquicklycalculatetheresultofA^BmodC.(1<=A,C<=1000000000,1<=B<=10^1000000).InputTherearemultiplytestcases.Ea...
HDU2824 The Euler function（欧拉函数）
题目求φ(a)+φ(a+1)+...+φ(b-1)+φ(b)。用欧拉筛选法O(n)计算出n以内的φ值，存个前缀和即可。φ(p)=p-1（p是质数），小于这个质数且与其互质的个数就是p-1；φ(p*a)=(p-1)*φ(a)（p是质数且p不能整除a），因为欧拉函数是积性函数，φ(p*a)=φ(p)*φ...
Codeforces_776E: The Holmes Children （数论 欧拉函数）
题目链接先看题目中给的函数f(n)和g(n)对于f(n)，若自然数对(x,y)满足x+y=n,且gcd(x,y)=1，则这样的数对对数为f(n)证明f(n)=phi(n)设有命题对任意自然数x满足x<n，gcd(x,n)=1等价于gcd(x,y)=1成立，则该式显然成立，下面证明这个命题。假设...
数学基础IV 欧拉函数 Miller Rabin Pollard's rho 欧拉定理 行列式
找了一些曾经没提到的算法。这应该是数学基础系最后一篇。曾经的文章：数学基础I莫比乌斯反演I莫比乌斯反演II数学基础II生成函数数学基础III博弈论容斥原理（hidden）线性基（hidden）卡特兰数/第二类斯特林数（hidden）置换群（hidden）莫比乌斯反演III（hidden）线性筛（hi...
Bzoj 2818: Gcd 莫比乌斯,分块,欧拉函数,线性筛
2818:GcdTimeLimit: 10Sec MemoryLimit: 256MBSubmit: 3241 Solved: 1437[Submit][Status][Discuss]Description给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多...
HDU6434 Count【欧拉函数 线性筛】
HDU6434I.CountT次询问，每次询问\(\sum_{i=1}^{n}\sum_{j=1}^{n-1}[gcd(i-j,i+j)=1]\)\(T\le1e5,n\le2e7\)对原式进行转换，枚举\(i-j\)，\(i-j\)为\(j\) ，那么可以变换为\(\sum_{i=1}^{n}\s...
Farey Sequence （素筛欧拉函数/水）题解
TheFareySequenceFnforanyintegernwithn>=2isthesetofirreduciblerationalnumbersa/bwith0<a<b<=nandgcd(a,b)=1arrangedinincreasingorder.Thefirst...