x+y+z<=k x+y+z+d=k 就等价于把k个东西放到4个框里，隔板法 因为可以为空所以先补4个空格，共k-1+4个空格，取3个隔板，分4份 即c（3，k-1+4） c（3，k+3）=（k+1）*（k+2）*（k+3）/6%m （k+1）*（k+2）/6*（k+3）会爆longlong，所以%m要放到（k+1）*（k+2）%m （k+1）*（k+2）*（k+3）/6%m 因为（k+1）*（k+2）*（k+3）%6=0 =（k+1）*（k+2）*（k+3）%（m*6）/6 =（k+1）*（k+2）%（m*6）*（k+3）...

https://www.acwing.com/problem/content/880/ 已知a,b,m，求解线性同余方程 代码 #include<bits/stdc++.h> using namespace std; typedef long long LL; int n,d,a,m,x,y,b; int exgcd(int a,int b,int &x,int &y){     if(!b){         x=1, y=0;         return a;     }     int d;     d=exgcd(b,a%b...

gcd(a,b)=gcd(b,a%b) gcd(a,b)中要求a，b是非负数 //xa+yb=gcd int exgcd(int a,int b,int &x,int &y){     if(!b){         x=1; y=0;         return a;  &nbsp...

1~n的和：（1+n）n/2 所以和在1~n中是n或者n/2的倍数 提出n（因为不是每个n都有n/2）有：（n-1）n/2 当n为奇数时：（n-1）是偶数，可以被2整除；只有n=1时例外，提出n后0和1gcd不满足，分析除本选法其他方法也没法实现 当n为偶数时：n和n/2除因数2以外还有其他因数，所以gcd>1；只有2例外，2和1gcd==1，分析除本选法外其他方法也没法实现 所以综上 #include <iostream> using namespace std; int n; int ...

证明如下： 1~n中 1的倍数：1/n 2的倍数：2/n .... n的倍数：n/n 所有【数-约数】对数加起来的总和： 平均每个数有ln（n）个约数

a*b=gcd*lcm for i：x~y 枚举每一个数     if （由两数乘积得出的另一个数存在 && gcd（i，另一个数）==n）  ans++； 代码： #include<bits/stdc++.h> using namespace std; int g,l,ans; int gcd(int a,int b){ return b?gcd(b,a%b):a; ...

欧拉函数φ（n）公式法 欧拉函数φ（n）表示：从1~n中与n互质数的个数 若对n进行质因数分解： 则欧拉函数公式： 理解Φ（n）=大小*（1-p1所占比重）*（1-p2所占比重）... 在充分混合的情况下，与所有pi都相异的比重=与p1相异的比重*与p2相异的比重*... 与pi相异的数的分布都是每pi个pi-1个，并且n是可以被整除，所以该式子一定能准确算出 时间复杂度：可知求一个数的φ（n）的瓶颈是分解质因数，为ln（n） 欧拉函数证明：（容斥定理） 1.从1~n中去掉p1、p2....pk的所有倍数 2.加...

找n！中p为因数次数 打质数表 对于每个质数p （向下取整） 代码： #include <bits/stdc++.h> using namespace std; const int N=1e6+6; int prime[N],mi[N],cnt,tmp,n,p; bool st[N]; void mTable(int n){ for(int i=2;i<=n;i++){ if(!st[i]) prime[cnt++]=i; f...

一个分数是否可以除尽 首先约分，1/2, 1/125可以除尽的原因是：十进制10=2*5->1/2,1000=2^3*5^3->1/125也就是10包括了2,125的所有质因数 b进制下，分母q是有限小数的充分条件是b有q的所有质因数 因此，这个问题就转化为了： 求b是否包含了q的所有质因子 一般是想到全部罗列再比较（超时）， 这里就可以用gcd的办法，找出两者gcd如果gcd可以整除q，则b包所有q的质因子 ——这里还可以优化下，就是b的除gcd以外的因子都没有用所有所以b=gcd 代码 #include&nbs...

对于任意正整数x，y，一定存在整数a，b，使得：    ax+by=gcd(x,y); 这里记得绝对值下 #include <bits/stdc++.h> using namespace std; int a,n,b,g; int gcd(int a,int b){ return b?gcd(b,a%b):a; } int main(int argc, char** argv) { cin>>...

我们先来看下什么情况是-1（无解）： 随便两个数3,4；就是无解，为什么因为要lcm%gcd=0，所以无解的情况就出来了 那么最小怎么满足呢 x和y必须是a的倍数，那么x最小就是a，那么此时y=lcm

计算n的约数（因数）之和： 设 约数之和 代码 #include<bits/stdc++.h> using namespace std; unordered_map<int,int> m; const int mod=1e9+7; long long  t,a,sum,ans; int main(){     cin>>t;     while(t--)...

思路 打素数表 for 遍历x1（即p2+1） ：x2-x2的最大质因数+1~x2     if i不是素数         x0=min（x0，x1-x1的最大质因数+1）     else x0=min（x0，x1）； 代码： #include <bits/stdc++.h> using namespace std; const&nbsp...

这个是大数（1e9）的小区间（1e6）的素数个数 埃氏n ln n大约2e7  预测400ms 线性打表2~根号n for i：素数表     for j:l~r中i最小的倍数~n         st[j]=true for 找出素数 代码： #include <bits/stdc++.h> using namespace std; const int N=...