[BZOJ 2820] YY的gcd(莫比乌斯反演+数论分块)
[BZOJ 2820] YY的gcd(莫比乌斯反演+数论分块)题面给定N, M,求\(1\leq x\leq N, 1\leq y\leq M\)且gcd(x, y)为质数的(x, y)有多少对。q组询问分析我们要求的是\[\sum_{p \in P} \sum_{i=1}^n \sum_{j=1}...
Codeforces #548 (Div2) - D.Steps to One（概率dp+数论）
Problem Codeforces #548 (Div2) - D.Steps to OneTime Limit: 2000 mSecProblem DescriptionInputThe first and only line contains a single integer mm (1≤...
[自用]数论和组合计数类数学相关（定理&证明&板子）
0 写在前面本文受 NaVi_Awson 的启发，有些地方相似，一些地方甚至直接引用，特此说明(感谢dalao)。1 数论1.0 gcd1.0.0 gcd$gcd(a,b) = gcd(b,a\;mod\;b)$证明：设 $c\mid a$，$c\mid b$，则 $c\mid (b-a)$。设 $...
UVa 11806 Cheerleaders (数论容斥原理)
题意：给定一个n*m的棋盘，要放k个石子，要求第一行，最后一行，第一列，最后一列都有石子，问有多少种放法。析：容斥原理，集合A是第一行没有石子，集合B是最后一行没有石子，集合C是第一列没有石子，集合D是最后一列没有石子，如果某一行或某一列，没有，那么就相当于减少一行或者一列。代码如下：#pragma...
Contest20140711 loop 数论
loop|loop.in|loop.out题目描述：有N个点。现在重复这样的操作：随机找一个出度为0的点p1，随机找一个入度为0的点p2，连一条有向边从p1指向p2。直到没有出度为0的点。统计最终状态这个图中的环的期望个数。为了保证答案精度，提供另外一个参数W（正整数），请你输出小于你的答案乘上W后...
数论F - Strange Way to Express Integers（不互素的的中国剩余定理）
F - Strange Way to Express IntegersTime Limit:1000MS Memory Limit:131072KB 64bit IO Format:%I64d & %I64uSubmit StatusDescriptionElina is r...
2.23日刷数论题后总结（题目整理自SCUT
第一道：Rightmost digit求N^N次最后一个数字快速幂mod10咯代码如下：#include <cstdio>#define ll long longusing namespace std;const int mod = ;int qm(ll a,ll b) { ll ...
「P4996」「洛谷11月月赛」 咕咕咕（数论
题目描述小 F 是一个能鸽善鹉的同学，他经常把事情拖到最后一天才去做，导致他的某些日子总是非常匆忙。比如，时间回溯到了 2018 年 11 月 3 日。小 F 望着自己的任务清单：看 iG 夺冠；补月赛题的锅。小 F 虽然经常咕咕咕，但他完成任务也是很厉害的，他一次性可以完成剩余任务的任一非空子集。...
Topcoder SRM 661 (Div.1) 250 MissingLCM - 数论
【题意】给你一个数N（1<=N<=10^6），要求最小的M（M>N），使得lcm(n+1,n+2,...m)=lcm(1,2,3,...,m)【思路】手速太慢啦，等敲完代码的时候发现比赛已经结束了一开始我想直接枚举m，并判断lcm(1,..,m)与lcm(n+1,n+2,...,m...
LOJ #2234. 「JLOI2014」聪明的燕姿（搜索 + 数论）
题意给出一个数 \(S\) ，输出所有约数和等于 \(S\) 的数。\(S \le 2 \times 10^9\) ，数据组数 \(\le 100\) 。题解首先用约数和定理：\[\begin{align}n &= \prod_{i} p_i^{a_i} \\\Rightarrow \sig...
Building a Space Station（kruskal,说好的数论呢）
Time Limit: 1000MS Memory Limit: 30000KTotal Submissions: 3820 Accepted: 1950DescriptionYou are a member of the space station engineering team, and ar...
【BZOJ】【2219】数论之神
中国剩余定理+原根+扩展欧几里得+BSGS题解：http://blog.csdn.net/regina8023/article/details/44863519新技能get√： LL Get_yuangen(LL p,LL phi){ int c=; for(int i=;i*i&l...
快速求n的质因子(数论)
快速求n的质因子如何尽快地求出n的质因子呢？我们这里又涉及两个好的算法了!第一个：用于每次只能求出一个数的质因子,适用于题目中给的n的个数不是很多，但是n又特别大的#include<stdio.h>int main(){ __int64 a[100],num,i,n; while...
洛谷P2231 [HNOI2002]跳蚤 [数论，容斥原理]
题目传送门跳蚤题目描述Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一...
hdu6390GuGuFishtion【数论】
GuGuFishtionTime Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1204 Accepted Submission(s): 45...
LOJ2803 CCC2018 平衡树 数论分块、记忆化搜索
传送门题意差评，其实就是一个递推式：\(f_1 = 1 , f_i = \sum\limits_{j=2}^i f_{\lfloor \frac{i}{j} \rfloor}\)，然后求\(f_N\)的值首先\(\lfloor \frac{i}{j} \rfloor\)只有\(2\sqrt{i}\)...
数论 - n元线性同余方程的解法
note:n元线性同余方程因其编程的特殊性，一般在acm中用的很少，这里只是出于兴趣学了一下n元线性同余方程的概念:形如：(a1*x1+a2*x2+....+an*xn)%m=b%m ..................(1)当然也有很多变形，例如：a1*x1+a2*x2+......
BZOJ-1013 球形空间产生器sphere 高斯消元+数论推公式
1013: [JSOI2008]球形空间产生器sphere Time Limit: 1 Sec Memory Limit: 162 MB Submit: 3662 Solved: 1910 [Submit][Status][Discuss]Description 有一个球形空间产生器能够在n维空...
牛客网Wannafly挑战赛25A 因子（数论 素因子分解）
链接：https://www.nowcoder.com/acm/contest/197/A来源：牛客网时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld题目描述令 X = n!, 给定一大于1的正整数p 求...
poj---（2886）Who Gets the Most Candies?（线段树+数论）
Who Gets the Most Candies?Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 10373 Accepted: 3224Case Time Limit: 2000MSDescriptionN children ...