前言 首先，根据欧拉函数的公式可以证明它是一个积性函数，于是有 ϕ ( a ∗ b ) = ϕ ( ...

euler函数： ϕ ( n ) = n ∗ ∏ ...

1014 Waiting in Line (30 分) Suppose a bank has NNN windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are: The space inside the yellow line in front of each window is enough...

转自http://blog.csdn.net/cc_again?viewmode=list 动态规划一直是ACM竞赛中的重点，同时又是难点，因为该算法时间效率高，代码量少，多元性强，主要考察思维能力、建模抽象能力、灵活度。 本人动态规划博客地址：http://blog.csdn.net/cc_again/article/category/1261899 ****************************************************************************************** 动态规划（英语：Dynamic progra...

转自 https://blog.csdn.net/Soul_97/article/details/86928393 区间最值 I Hate It                           ★☆☆☆☆   最值-单点更新，批量查询 Sticks Problem                      ★★☆☆☆   最值-二分枚举 + 批量查询 Balanced Lineup                     ★★☆☆☆   最值-批量查询 Frequent values                     ★★☆☆☆   最值-批量查询 B...

转自 https://blog.csdn.net/Soul_97/article/details/87904163  1、素数和因数分解      Largest prime factor   ★☆☆☆☆        素数筛选      The number of divisors ★☆☆☆☆        因子数      七夕节                  ★☆☆☆☆        因子和      Happy 2004             ★☆☆☆☆        X^Y的因子和      Number Sequence        ★☆☆☆...

思路：约数和定理 关于二分法： Code: #include <bits/stdc++.h> #define mod 9901 #define rep(i,a,b) for (int i=a; i<=b; i++) using namespace std; int qpow (int a, int b) { int ans = 1; a %= mod; while (b) { if (b & 1) { ans = ans * a % mod; } a = a * a % mod; b >>= 1; } return...

转自 https://blog.csdn.net/controlbear/article/details/77527115 刚才手动推了一下 用线性筛筛约数个数和约数和，就顺便写篇博客记录一下。不过网上应该也有不少人推过了。 根据算术基本定理我们可以知道，每一个大于等于2的正整数，都可以被分解成这种形式。 ,其中 p 为素数。 线性筛就是每一次被最小素因子给筛出。 线性筛写法 (只筛素数) [我个人比较常用] const int N= 1e5+ 5; ...

转自https://www.cnblogs.com/aininot260/p/9574789.html POJ1845 首先把A写成唯一分解定理的形式 分解时让A对所有质数从小到大取模就好了 然后就有：A = p1^k1 * p2^k2 * p3^k3 *...* pn^kn 然后有： A^B = p1^(k1*B) * p2^(k2*B) *...* pn^(kn*B); 约数和公式： 对于已经分解的整数A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn) 有A的所有因子之和为   S = (1+p1+p1^2+p1^3+...p...

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2271 思路：除去两题水题以及那两题想偏了的数学期望题就这题能做…(越学越菜了。很容易想到floyd的做法，但当两点之间有路并且除他之外有一条最短路，本条路一定能除去这个思维点不好想。 Code： //一份思路还不错的代码 #include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<iostream> using namespace st...

题目链接：七夕节 思路：这题数据规模不大，用下这个定理1A Code： #include <math.h> #include <stdio.h> const int mod = 1e9+7; int qpow (int a, int b) { int ans = 1; while (b) { if (b & 1) { ans = ans * a % mod; } a = a * a % mod; b >>= 1; } return ans; } int solve (int n) { int sum = 1...

转自https://www.cnblogs.com/bolderic/p/7406204.html 一些常用的简单数论模板以及书中的定理   组合数取模 1：N M < 1000， 杨辉三角双循环，边加边取模（代码未添加取模） 1 c[1][1] = c[1][0] = 1; 2 for(int i = 2; i <= 50; i++){ 3 c[i][0] = 1; 4 for(int j = 1; j <= i; j++){ 5 c[i][j] = (c[i - 1][j - 1] + c[...

1013 Battle Over Cities （25 分) It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities c...