【NOIP训练】【规律+数论】欧拉函数的应用
Problem1【题目大意】给出多组数据，给出 求出。题解证明: 除了以为均为偶数，所以互质的个数成对。由得。所以对于每对的和为，共有对。则Problem2【题目大意】在第一个圆上写入 ，在第二个圆上写入，此后每一次在前一个圆的基础上，每两个数之间写上他们的和，定义为第i个圆中数字i的个数。给出，求...
【数论】【枚举】【莫比乌斯反演】【线性筛】bzoj2818 Gcd
思路是hdu6134的简化版，只需要在外面套上一个枚举素数就行了。http://www.cnblogs.com/autsky-jadek/p/7491730.html#include<cstdio>usingnamespacestd;#defineN10000000boolnotpri[...
51Nod1222 最小公倍数计数 数论 Min_25 筛
原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1222.html题意给定$a,b$，求$$\sum_{n=a}^b\sum_{i=1}^n\sum_{j=1}^i[{\rmlcm}(i,j)=n]$$$$a,b\leq10^{11}$$$${\rmT...
hdu 4542 数论 + 约数个数相关 腾讯编程马拉松复赛
题目：http://acm.hdu.edu.cn/showproblem.php?pid=4542小明系列故事——未知剩余系TimeLimit:500/200MS(Java/Others) MemoryLimit:65535/32768K(Java/Others)TotalSubmission...
code forces 382 D Taxes（数论--哥德巴赫猜想）
Taxestimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputMr.Funtnowlivesinacountrywithaveryspecifictaxlaws.The...
BZOJ 2705: [SDOI2012]Longge的问题( 数论 )
T了一版....是因为我找质因数的姿势不对...考虑n的每个因数对答案的贡献.答案就是∑d*phi(n/d)(d|n)直接枚举n的因数然后求phi就行了.但是我们可以做的更好.注意到h(n)= ∑d*phi(n/d)(d|n)是狄利克雷卷积的形式,而且f(x)=x和f(x)=phi(x)都是积性函数...
2018.10.05 NOIP模拟 阶乘（简单数论）
传送门签到题。直接把所有数先质因数分解。同时统计每一个在阶乘中会出现的质数出现的最少次数。然后对于每一个这样的质数，我们求出满足其出现质数的m的最小值，然后求出所有m的最大值。求m的时候可以用二分求。代码2018.10.05NOIP模拟阶乘（简单数论）的更多相关文章2018.1...
[Swust OJ 1125]--又见GCD(数论，素数表存贮因子)
题目链接：http://acm.swust.edu.cn/problem/1125/Timelimit(ms):1000Memorylimit(kb):65535 Description哈特13最近在学习数论问题，然后他智商太低，并学不懂。这不，他又碰到不会的题了。题意非常简单：有n个数字，求出这些...
UVA 10303 - How Many Trees?(数论 卡特兰数 高精度）
ProblemDHowManyTrees?Input: standardinputOutput: standardoutputMemoryLimit: 32MBAbinarysearchtreeisabinarytreewithroot k suchthatanynode v intheleftsu...
hdu 5478 （数论）
题意：给定 C，k1,b1,k2 找出所有的（a,b）满足 ak1⋅n+b1+ bk2⋅n−k2+1 =0(modC)(n=1,2,3,...) （1<=a,b<C）1. 当n=1时，a^(k1+b1)+b=0(modC) => a^(2*k1+b1)+b*a^(k1)=0(mo...
【数论】UVa 11526 - H(n)
WhatisthevaluethissimpleC++functionwillreturn?longlongH(intn){longlongres=;for(inti=;i<=n;i=i+){res=(res+n/i);}returnres;}InputThefirstlineofinputi...
ACM数论之旅11---浅谈指数与对数（长篇）（今天休息，不学太难的数论＞ 3＜）
c/c++语言中，关于指数，对数的函数我也就知道那么多exp(),pow(),sqrt(),log(),log10(),exp(x)就是计算e的x次方，sqrt(x)就是对x开根号pow()函数可是十分强大的(￣ε￣)pow(a,b)可以算a的b次方，但是b不限于整数，小数也可以所以pow(x,0....
《Mathematical Olympiad——数论》——整除
数论这个东西吧，虽说也是高中IMOer玩的数学游戏，颇具美学性的证明比较多。就目前所知，它在算法里是一些加密技术的基础，不多言，开始具体题目的分析。问题一：已知数列{an},且a0=2,a1=1,a(n+1)=an+a(n-1)，证明：若p为a(2k)-2的素因子，则p也为a(2k+1)-1的素因子...
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...
【BZOJ1876】[SDOI2009]SuperGCD（数论，高精度）
【BZOJ1876】[SDOI2009]SuperGCD（数论，高精度）题面BZOJ洛谷题解那些说数论只会\(gcd\)的人呢？我现在连\(gcd\)都不会，谁来教教我啊？显然\(gcd\)除了辗转相除之外还可以辗转相减，然而辗转相减对于这题而言显然还不够优秀。我们这样子来做。如果当前\(a,b\)...
ACM数论之旅6---数论倒数，又称逆元（我整个人都倒了(￣﹏￣)）
数论倒数，又称逆元（因为我说习惯逆元了，下面我都说逆元）数论中的倒数是有特别的意义滴你以为a的倒数在数论中还是1/a吗(・∀・)哼哼~天真先来引入求余概念(a+ b)%p=(a%p+ b%p)%p （对）(a - b)%p=(a%p - b%p)%p （对）(a * b)%p=(a%p* b%p)%...
hdu 2608 （数论）
hdu2608 0or1题意：给你一个数N（N<2^31）,问从1--N所有数的因子和S(N)，求S(N)%2的值。链接：http://acm.hdu.edu.cn/showproblem.php?pid=2608思路：参考了下其它博客，自己总结如下：对于每一个数N，我们可以将其拆分为 N=2...
acm数论之旅（转载） -- 逆元
ACM数论之旅6---数论倒数，又称逆元（我整个人都倒了(￣﹏￣)） 数论倒数，又称逆元（因为我说习惯逆元了，下面我都说逆元）数论中的倒数是有特别的意义滴你以为a的倒数在数论中还是1/a吗(・∀・)哼哼~天真先来引入求余概念(a+ b)%p=(a%p+ b%p)%p （对）(a - b)%p=(a%...
hdu5184 数论证明
这题说的给了一个整数n和一串的括号，那么要我们计算最后有n/2对括号的方案数有多少。我们可以先预先判断一些不可能组成正确括号对的情况，然后我们可以将这个问题转化到二维平面上，令m=n/2 ，L为左括号的个数R为右括号的个数 可以知道还有m-L个左括号没用，有m-R个右括号没用，令他们分别我p=m-R...
ACM数论之旅17---反演定理 第一回 二项式反演（神说要有光 于是就有了光(´・ω・`)）
终于讲到反演定理了，反演定理这种东西记一下公式就好了，反正我是证明不出来的~(～o￣▽￣)～o首先，著名的反演公式我先简单的写一下o(￣ヘ￣*o)比如下面这个公式f(n)=g(1)+g(2)+g(3)+...+g(n)如果你知道g(x)，蓝后你就可以知道f(n)了如果我知道f(x)，我想求g(n)怎...