数论
数论小知识：
x|y 表示y能被x整数
1-n中的数的因子个数最大为n的二进制位数。看题：https://ac.nowcoder.com/acm/contest/8282/A
n内既是2的倍数又是3的倍数的个数有： n/lcm(2,3)个
阶乘
https://ac.nowcoder.com/acm/problem/22942
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#define ll long long
#define inf 0x3f3f3f3f
const int mod = 1e9+7;
using namespace std;
int main()
{
int n;
cin>>n;
ll ans = 1;
for(ll i = 1; i <= n; i ++)
{
ans *= i;
while(ans % 10 == 0)
ans /= 10;
ans = ans%1000;
}
cout<< ans%10 <<endl;
return 0;
}
//线性筛选
void init()
{
cnt = 0;
for(i = 2; i <= N; i++){
if(!v[i]){
cnt++;
prime[cnt] = i;
v[i] = i;
}
for(j = 1; j <= cnt; j++){
if(prime[j] * i > N) break;
v[i * prime[j]] = prime[j];
if(i % prime[j] == 0) break;
}
}
} 埃氏筛选法 （限制条件 n <= 1e7）
void init()
{
int visit[1000005],print[1000005];
for(int i = 2; i * i <= n; i++){
if(!visit[i]){
for(int j = i*i; j <= n; j += i){
visit[i] = 1;
}
}
}
int cnt = 0;
for(int i = 1; i <= n; i++){
if(visit[i]){
prime[++cnt] = i;
}
}
} 大数筛选：l-r之间的素数个数 #include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
int prime_a[10000010],prime_b[10000010];
void getprime(int l,int r)
{
for(int i = 2; i * i <= r; i++){
if(!prime_a[i]){
for(int j = 2*i; j * j <= r; j += i){
prime_a[j] = 1;
}
int k = max(2,(l+i-1)/i);
for(int j = k*i; j <= r; j += i){
if(k != 1) prime_b[j - l] = 1;
}
}
}
}
int main()
{
int l,r;
scanf("%d%d",&l,&r);
getprime(l,r);
int cnt = 0;
for(int i = l; i <= r; i++){
if(!prime_b[i-l]) cnt++;
}
printf("%d\n",cnt);
return 0;
} 求一个数的所有因子(1e15的因子个数为256)
void init(ll n)
{
for(ll i = 1; i*i <= n; i++){
if(n % i == 0){
yz[cnt++] = i;
if(n/i != i) yz[cnt++] = n/i;
}
}
} 欧拉函数:求1~N中与N互质的个数
算数基本定理：任何一个大于1的正整数N都可以唯一分解成有限个质数的乘积，N=p1^c1p2^c2...pm^cm,p1...pm都是质数且递增。O(n) = N*(p1-1)/p1......(pm-1)/pm
性质：如果a,b都是质数，则f(a*b) = f(a) * f(b);
欧拉函数的一些性质：
1)如果x为质数，则f(x) = x - 1
2)如果x%p == 0，则f(x * p) = f(x) * p
3)f(a * b) = f(a) * f(b)
重要知识：假设gcd(i,j) = d (1 =< i,j <= n),那么我们就去找有多少个i，j满足gcd(i,j) = d，其实等价于gcd(i,j) = 1 (1 =< i,j <= n/d),也就是要找在这个区间内有多少对i，j互质。为什么呢，因为i，j都小于n/d, 而n/d*d <= n,那么i*d和j*d也一定小于等于n，而i，j互质，那么i*d和j*d的最大公约数就是d。
void init()
{
int i,j;
for(i = 2; i <= 3000000; i++){
if(phi[i] == 0){
cnt++;
phi[i] = i - 1;
prime[cnt] = i;
}
for(j = 1; j <= cnt; j++){
if(i * prime[j] > 3000000) break;
if(i % prime[j] == 0){
phi[i * prime[j]] = phi[i] * prime[j];
}
else{
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
if(i % prime[j] == 0) break;
}
}
} 按公式：第二种更快
ll eular(ll n)
{
ll ans = n;
for(int i=2; i*i <= n; ++i)
{
if(n%i == 0)
{
ans = ans/i*(i-1);
while(n%i == 0)
n/=i;
}
}
if(n > 1) ans = ans/n*(n-1);
return ans;
} void euler()
{
for(int i = 2; i < maxn;i++){
if(!E[i])
for(int j = i; j <maxn; j += i){
if(!E[j]) E[j]=j;
E[j] = E[j]/i * (i-1);
}
}
} 二项分布
一般地，在n次独立重复试验中，ξ表示事件A发生的次数。如果事件A发生的概率是p，则不发生的概率 q=1-p，n次独立重复试验中，事件A发生k次的概率是：P(ξ=k)=C(n,k)*p^k*(1-p)^(n-k)
(k=0,1,2,3…n），那么就说ξ服从参数p的二项分布，其中p称为成功概率。记作：ξ~B(n,p)。
(k=0,1,2,3…n），那么就说ξ服从参数p的二项分布，其中p称为成功概率。记作：ξ~B(n,p)。
（1）二项分布ξ的期望：Eξ=np；
（2）二项分布ξ的方差：Dξ=npq。
几何分布
在第n次伯努利试验中，ξ表示是事件A第一次成功的试验的第次，详细的说是：前ξ-1次皆失败，第ξ次成功。如果事件A发生的概率是p，则不发生的概率q=1-p，n次独立重复试验中，第k次试验是事件A的第一次成功的概率是：P(ξ=k)=p*(1-p)^(k-1);
那么就说ξ 服从参数p的几何分布，其中p称为成功概率。
（1）几何分布的期望Eξ=1/p;
（2）几何分布的方差Dξ=(1-p)/p^2;
容斥原理
偶数相减，奇数相加。
可以求1-n中与m互质的个数
二进制枚举版：
int rc()
{
int p = 0,syz,sum = 0;
int k = (1 << cnt);
//cout << k << endl;
for(int i = 1; i < k; i++){
syz = 1;
p = 0;
for(int j = 0; j < 32; j++){
if(i & (1 << j)) p++, syz *= prime[j];
}
if(p & 1) sum += n / syz;
else sum -= n / syz;
}
return sum;
} dfs版：
// xb表示当前素因子下标，cj表示素因子乘积，num表示所选个数。
void dfs(int xb,int cj,int num)
{
if(num & 1) sum += n / cj;
else sum -= n / cj;
for(int i = xb + 1; i < cnt; i++){
dfs(i,cj*prime[i],num+1);
}
}
for(int i = 0; i < cnt; i++){
dfs(i,prime[i],1);
} 如果两个点坐标的连线上没有其他点，那么这两个点对应坐标的差值互质。而这题一个点已经确定是（0,0），那么只要找一个坐标（x,y），有gcd（x，y） = 1，即1-n中与1-m中的数互质的个数。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int t,n;
int prime[105],cnt;
int rc()
{
int p = 0,syz,sum = 0;
int k = (1 << cnt);
//cout << k << endl;
for(int i = 1; i < k; i++){
syz = 1;
p = 0;
for(int j = 0; j < 32; j++){
if(i & (1 << j)) p++, syz *= prime[j];
}
if(p & 1) sum += n / syz;
else sum -= n / syz;
}
return sum;
}
int solve(int m)
{
memset(prime,0,sizeof(prime));
for(int i = 2; i*i <= m; i++){
if(m % i == 0){
prime[cnt++] = i;
while(m % i == 0){
m /= i;
}
}
}
if(m > 1) prime[cnt++] = m;
//cout << cnt << endl;
return rc();
}
int main()
{
ios::sync_with_stdio(false);
int m;
cin >> t;
while(t--){
cin >> n >> m;
ll sum = 0;
for(int i = 1; i <= m; i++){
cnt = 0;
sum += n - 1ll*solve(i);
}
cout << sum << endl;
}
return 0;
} 扩展欧几里得
求整数解x,y使得ax + by = m,有解得前提条件是m % gcd(a,b) == 0。
证明：a = gcd(a,b)*a1,b = gcd(a,b)*b1
则gcd(a,b)*(a1*x + b*y) = m,要a1,b1,x,y都是整数则m % gcd(a,b) == 0。
求出一组整数解(x0,y0)
通解：
x = x0 + b*t
y = y0 - a*t
a = a / gcd(a,b)
b = b / gcd(a,b)
当方程符合ax + by = gcd(a,b)是，可以求出一组整数解
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if(b == 0){
x = 1;
y = 0;
return a;
}
long long d = exgcd(b,a%b,y,x);
y = y - a/b*x;
return d;
} 逆元
ax = 1 (mod m)
求逆元代码：
1）
x = qpow(a,m - 2);2)
int inv(int a,int m)
{
int x,y,t;
t = exgcd(a,m,x,y);
return (a%m + m) % m;
} 一个小问题：中国剩余定理
1)中国剩余定理：求一个数x 使得x = a1 (mod m1),x = a2 (mod m2)...x = an (mod m(n)),并且m1,m2...mn两两互质。
M = m1*m2...mn,M1 = M/m1,那么x = (a1*M1*t1 + a2*M2*t2 + ...+ an*Mn*tn),(其中ti 为Mi*ti = 1(mod mi)的一个解，即为Mi在模mi下的逆元)，代入验证可发现成立。
2)扩展中国剩余定理：m1,m2...mn不满足两两互质。
x = a1 (mod m1)
x = a2 (mod m2)
...
x = a1 + m1 * k1...........(1)
x = a2 + m2 * k2...........(2)
(1) - (2)
d = gcd(m1,m2)
m1 * k1 = a2 - a1 + m2 * k2
m1 * k1 = a2 - a1 (mod m2)
m1/d * k1 = (a2 - a1) / d (mod m2 / d)
k1 = inv(m1/d,m2/d) * (a2 - a1) / d (mod m2 / d)
代入(1)
x = a1 + m1 * inv(m1/d,m2/d) * (a2 - a1) / d (mod m2 / d)
即x = a1 + m1 * inv(m1/d,m2/d) * (a2 - a1) / d + (m1*m2)/d
即:
a1 += inv(m1/d,m2/d) * (a2 - a1) / d % (m2 / d) * m1
m1 = m1*m2 / d
一定要记住这两个公式
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#define ll long long
#define inf 0x3f3f3f3f
const int mod = 1e9+7;
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b == 0){
x = 1;
y = 0;
return a;
}
ll d = exgcd(b,a%b,y,x);
y = y - (a/b)*x;
return d;
}
ll gcd(ll a,ll b)
{
return b == 0 ? a : gcd(b,a%b);
}
ll a[100005],b[100005];
int main(){
int k,flag = 1;
cin >> k;
for(int i = 0; i < k; i++) cin >> a[i] >> b[i];
for(int i = 1; i < k; i++){
ll x,y;
ll g = gcd(a[0],a[i]);
if((b[i] - b[0]) % g != 0){
flag = 0;
break;
}
ll d = exgcd(a[0]/g,a[i]/g,x,y);
x = (x + a[i]) % a[i];
b[0] += x * ((b[i] - b[0]) / g) % (a[i] / d) * a[0];
a[0] = a[0] / g * a[i];
}
if(!flag) cout << "-1";
else cout << b[0];
return 0;
} 更相减损法
int gcd(int a,int b)
{
if(a==b)
return a;
if(a>b)
return gcd(a-b,b);
if(a<b)
return gcd(b-a,a);
}
题目：
中秋节快到了，rrz想去找她的好朋友。
rrz所在的地图是一个二维坐标系，她所在的位置是(x,y)，她的好朋友的位置是(x′,y′)。
rrz受限于交通工具的影响，假设他当前位置是(x,y)(x,y),他每次所能走到的地方是(x−y,y),(x+y,y)(x,x+y),(x,y−x);
问你rrz是否能成功找到她的好朋友。
int main(){
int t;
cin>>t;
while(t--){
ll a,b,c,d;
cin>>a>>b>>c>>d;
if(gcd(a,b)==gcd(c,d)){
printf("1\n");
}
else{
printf("0\n");
}
}
} 数论(整除)分块
题目类型 ：求
n/i 下取整。
int main()
{
int l,r,ans = 0;
for(l = 1; l <= n; l = r+1){
if(n/l) r = n/(n/l);
else r = n;
ans += (r-l+1)*(n/l);
}
return 0;
} 求
n%i = n-n/i*i
原式 = 
方程解
前置知识：
无解的情况是%20!%3D%201)
,因为非齐次线性方程组无解的情况是%20%3C%20r(A%2Cb))
系数矩阵的秩小于增广矩阵的秩.否则就有解
大意：给出一组数，每个数无限多个，问这些数不能组成的数有多少个。
思路：，无解
否则：前i项能凑到的数为前面1-（i-1）项每一项的倍数和+第i项的倍数和。模拟一遍就能明白了。
for(int j = 0; j <= 10000; j++){
if(vis[j]) vis[j+a[i]] = 1;
} #include <bits/stdc++.h>
#define ll long long;
const int N = 1e6+7;
const int mod = 1e9+7;
using namespace std;
int gcd(int x,int y){
if(y == 0) return x;
else return gcd(y,x%y);
}
int a[N],vis[N];
void solve(){
int n,g;
cin >> n;
vis[0] = 1;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++){
if(i == 1) g = a[i];
else g = gcd(g,a[i]);
for(int j = 0; j <= 10000; j++){
if(vis[j]) vis[j+a[i]] = 1;
}
}
if(g != 1) cout << "INF\n";
else {
int ans = 0;
for(int i = 1; i <= 10000; i++){
if(vis[i] == 0) ans++;
}
cout << ans << endl;
}
}
int main(){
// int t;
// cin >> t;
// while(t--)
solve();
//system("pause");
return 0;
} 拜托了，牛老师
涉及算法：dfs，STL
思路：
1）一般二进制枚举实现不了的要想到用dfs去做
2）利用栈和队列的特性将所有因子按从小到达顺序存储。
3）依次由每一个因子去更新答案，并且选当前这个因子后，之后的因子从后面找，这样可以避免重复。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
using namespace std;
//void print(char a[])
//{
// printf("%d %c\n",strlen(a),a[2]);
//}
vector<int>a;
stack<int>s;
queue<int>q;
int mmin = mod;
void dfs(int val,int st,int sum)
{
if(val == 1){
mmin = min(mmin,sum);
return;
}
for(int i = st; i < a.size() && a[i] <= val; i++){
if(val % a[i] == 0){
dfs(val / a[i],i+1,sum + a[i]);
}
}
}
int main()
{
int n;
cin >> n;
for(int i = 2; i * i <= n; i++){
if(n % i == 0){
q.push(i);
}
if(n % i == 0 && n / i != i){
s.push(n/i);
}
}
mmin = n + 1;
//利用栈和队列的特性实现因子从小到达排序。
while(!q.empty()) {
int t = q.front();
q.pop();
a.push_back(t);
}
while(!s.empty()){
int t = s.top();
s.pop();
a.push_back(t);
}
cout << endl;
dfs(n,0,0);
cout << mmin;
return 0;
} Distance：公式变形
思路：去掉绝对值有四种情况
i*i - j*j + ai*ai - aj*aj......1
i*i - j*j + aj*aj - ai*ai......2
j*j - i*i + ai*ai - aj*aj......3
j*j - i*i + aj*aj - ai*ai......4
其实是两种类型：
1和4：i*i + ai*ai - (j*j + aj*aj)
2和3：i*i - ai*ai - (j*j - aj*aj)
所有我们先求i*i + ai*ai放入一个数组 然后让最大值减去最小值
再求i*i - ai*ai，同上，两者取最值得answer。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int t,n,ans = 0;
ll a[100005],m1[100005],m2[100005];
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) m1[i] = 1ll*i*i + a[i]*a[i];
for(int i = 1; i <= n; i++) m2[i] = 1ll*i*i - a[i]*a[i];
sort(m1+1,m1+n+1);
sort(m2+1,m2+n+1);
cout << max(m1[n]-m1[1],m2[n]-m2[1]);
return 0;
} 计算几何
公式：maxs = Π*b*b + Π*(a-b)*(a-b)
先求以第二长的边为半径的圆的面积，再求第一长减去第二长的圆的面积。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
//#include <set>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int T,n;
cin >> T;
while(T--)
{
int a,b,c;
cin >> a >> b >> c;
//保证a<b<c;
if(a > b){
int temp = a;
a = b;
b = temp;
}
if(a > c){
int temp = a;
a = c;
c = temp;
}
if(b > c){
int temp = b;
b = c;
c = temp;
}
printf("%.12f\n",p*b*b+p*(c-b)*(c-b));
}
return 0;
} 所有情况的和
根据乘法原理(a1+b1)*(a2+b2)*......*(an+bn)拆开可得原式子。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int a[1005],b[1005],dp[1005][2],n;
int sum = 0;
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
int ans = 1;
for(int i = 1; i <= n; i++){
ans = (ans % mod * (a[i] + b[i]) % mod) % mod;
}
cout << (ans) % mod;
return 0;
} 永远亭的小游戏
和上一题一样，注意取模和开 long long
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const ll mod = 1e9+7;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll qpow(ll a,ll b)
{
ll res = 1;
a %= mod;
while(b)
{
if(b&1) res = res*a%mod;
a = a*a%mod;
b >>= 1;
}
return res%mod;
}
int main()
{
ll n,m,k,x;
ll sum1 = 0,sum2 = 0,sum3 = 0,b;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i = 1; i <= n; i++) scanf("%lld",&x),sum1 = (sum1+x)%mod;
for(int i = 1; i <= m; i++) scanf("%lld",&x),sum2 = (sum2+x)%mod;
for(int i = 1; i <= k; i++) scanf("%lld",&x),sum3 = (sum3+x)%mod;
sum1 = (sum1%mod*sum2%mod)%mod*sum3%mod;
b = (n%mod*m%mod)%mod*k%mod;
b = qpow(b,mod-2);
cout << (sum1%mod*b%mod)%mod;
return 0;
} 数一（2）
思路：十进制转化成k进制是除k反向取余，又因为我们要求有多少个一，那么直接除k取余看有多少个一就好了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int a[1005],b[1005],dp[1005][2],n,k;
int judge(int i)
{
int cnt = 0;
while(i){
int t = i % k;
i /= k;
if(t == 1) cnt++;
}
return cnt;
}
int main()
{
ios::sync_with_stdio(false);
while(cin >> n >> k){
ll sum = 0;
for(int i = 1; i <= n; i++){
sum += judge(i);
}
cout << sum << endl;
}
return 0;
}
环形涂色问题
n个扇形，m种颜色可选，要求相邻两个扇形所涂颜色不同。
公式: (-1)^n*(m-1) + (m-1)^n
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e8+7;
const double p = 3.141592653589793238462643383;
using namespace std;
//sum[r] - sum[r-l+1] = j*j
ll qpow(ll a,ll b)
{
ll res = 1;
while(b){
if(b & 1) res = res *a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
ll t,n,k;
cin >> t;
while(t--){
ll ans;
cin >> n >> k;
if(n % 2 == 0){
ans = k - 1 + qpow(k - 1,n);
}
else ans = 1 - k + qpow(k - 1,n);
cout << ans << endl;
}
return 0;
}
珂朵莉与数列
对与每个区间的和有公式：sum[r] - sum[l - r + 1]
所有只要sum[r] - sum[l-r+1] = k*k
变形: sum[r] - k*k = sum[l-r+1]
看看有多少个区间和是sum[l-r+1]就可以。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double p = 3.141592653589793238462643383;
using namespace std;
//sum[r] - sum[r-l+1] = j*j
int main()
{
ios::sync_with_stdio(false);
int n,sum,x,num[5000005];
ll ans = 0;
cin >> n;
num[0] = 1;
sum = 0;
for(int i = 1; i <= n; i++){
cin >> x;
sum += x;
for(int j = 0; j * j <= sum; j++){
ans += 1ll*num[sum - j * j];
}
num[sum]++;
}
cout << ans << endl;
return 0;
} 集合中的质数：容斥原理
思路：因为集合中全为质数，那么所有数相乘后得到的数n，将这个数质因数m分解就是集合所有书相乘，即问题转化为，求1-m中与n不互质的个数，即能n被1-m中的数整除的个数。我们又知道一个数pi，1-m的数能被pi整除的个数为m/pi向下取整。
http://acm.hdu.edu.cn/showproblem.php?pid=4135
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int n,m,a[25];
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
ll sum = 0,res;
int num = (1 << n);
for(int i = 1; i < num; i++){
res = 1;
ll cnt = 0;
for(int j = 0; j < 32; j++){
if(i & (1 << j)) cnt++,res *= 1ll*a[j + 1];
}
if(cnt & 1) sum += 1ll*m / res;
else sum -= 1ll*m / res;
}
cout << sum << endl;
return 0;
} 约数的个数
1-n中能被p整数的数为 n/p向下取整。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>a
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int n,m;
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
ll sum = 0;
for(int i = 1; i <= n; i++){
sum += n / i;
}
cout << sum << endl;
return 0;
} 牛牛的算术：找规律，前缀和
思路：
1：首先按照样例列出几个式子，看他的规律。
2：如2,(1*1*1)*(2*1*1+2*2*1+2*2*2) = (1*2)*(1*1)*(1*1+1*2+2*2) = (1*2)*(1*sum[1])*(1*sum[1]+2*sum[2])
3,(1*1*1)*(2*1*1+2*2*1+2*2*2)*(3*1*1+3*2*1+3*2*2+3*3*1+3*3*2+3*3*3) = (1*2*3)*(1*sum[1])*(1*sum[1]+2*sum[2])*(1*sum[1]+2*sum[2]+3*sum[3])
3：因为有阶乘在，那么当n大于等于mod1的时候，取模一定是零，所有当看到mod很小的时候可以往取模为零的方向想。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int mod1 = 199999;
ll mul[200000],sum[200000],jc[200000];
void init()
{
mul[1] = 1;
sum[1] = 1,jc[1] = 1;
ll temp = 1;
for(int i = 2; i <= 200000; i++){
sum[i] = (sum[i - 1] % mod1 + i % mod1) % mod1;
temp = temp % mod1 + i * sum[i] % mod1;
//jc[i] = (jc[i - 1] % mod1 * i % mod1) % mod1;不需要求阶乘，只需要把i乘上即可，因为mul[i-1]已经包含了1*2*...*(i-1).
mul[i] = (mul[i - 1] % mod1 * i % mod1 * temp % mod1) % mod1;
}
}
int main()
{
ios::sync_with_stdio(false);
int t;
string s;
init();
cin >> t;
while(t--){
cin >> s;
int l = s.length();
if(l > 6) cout << 0 << endl;
else{
ll n = 0;
for(int i = 0; i < l; i++){
n = n * 10 + s[i] - '0';
//cout << n << endl;
}
cout << mul[n] % mod1 << endl;
}
}
return 0;
} 第九届蓝桥杯国赛-矩阵求和：欧拉函数
思路：
1）不能直接暴力求解出矩阵的元素，根据其定义可知[i,j]的元素为gcd(i,j)*gcd(i,j)。
2）假设gcd(i,j) = d (1 =< i,j <= n),那么我们就去找有多少个i，j满足gcd(i,j) = d，其实等价于gcd(i,j) = 1 (1 =< i,j <= n/d),也就是要找在这个区间内有多少对i，j互质。为什么呢，因为i，j都小于n/d, 而n/d*d <= n,那么i*d和j*d也一定小于等于n，而i，j互质，那么i*d和j*d的最大公约数就是d。
3）用欧拉函数去找[1-i]内与i互质的个数，同时乘上而，因为这个矩阵是对称的。
4）1<=i<=n/d,所以递推出s[i] = s[i-1]+2*phi[i]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
//const double p = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
int phi[10000007],prime[10000007],cnt = 0;
ll s[10000007];
void oula()
{
phi[1]=1;
for(int i = 2; i < 10000007; i++){
if(!phi[i]){
phi[i] = i - 1;
prime[cnt++] = i;
}
for(int j = 0; j < cnt; j++){
if(i * prime[j] > 10000007) break;
if(i % prime[j] == 0){
phi[i*prime[j]] = phi[i]*prime[j];
break;
}
else phi[i*prime[j]] = phi[i]*phi[prime[j]];
}
}
s[1] = phi[1];
for(int i = 2; i <= 10000007; i++){
s[i] = s[i-1]+2*phi[i];
}
}
int main()
{
int n;
oula();
//cout << phi[4] << endl;
cin >> n;
ll sum = 0;
for(int i = 1; i <= n; i++){
//sum += phi[i/2]*i*i;
sum = (sum%mod + s[n/i]%mod*i%mod*i%mod)%mod;
}
cout << sum % mod << endl;
return 0;
} n和m不同的题
小A的数学题
这个解法用在上面会超时，猜测数据范围要在 1e6以内
公约数为t的个数为 t = (n/t)*(m/t),但是要减去最大公约数为t的倍数的个数。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll f[1000005]={0};
int main(){
ll n,m,i,j;
cin>>n>>m;
ll ans=n>m?m:n,sum; //ans取n和m当中小的那一个
sum=0;
for(i=ans;i>=1;i--){ // 对于每一个 gcd=i的贡献（出现的次数）计算
f[i]=(ll)(n/i)*(ll)(m/i);
for(j=i+i;j<=ans;j=j+i)
f[i]=f[i]-f[j];
sum=(sum+f[i]*(i*i%mod)%mod)%mod; //疯狂取模防止爆 long long
}
cout<<sum<<endl;
return 0;
} 
华为工作强度 834人发布