数论

数论小知识：
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)。
（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;


头文件<algorithm>里的__gcd(x,y)可以用来求两个数的最大公约数。

容斥原理

偶数相减，奇数相加。
可以求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
原式 =

方程解

前置知识：无解的情况是,因为非齐次线性方程组无解的情况是 系数矩阵的秩小于增广矩阵的秩.否则就有解
大意：给出一组数，每个数无限多个，问这些数不能组成的数有多少个。
思路：，无解
否则：前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;
}







全部评论

相关推荐

不愿透露姓名的神秘牛友
11-27 15:35
同事在会议室扇了自己好几个大嘴巴子
昨天晚上十点多，公司群里领导发了一份表格，让我们都填一下。&nbsp;那个表格有问题，死活打不开，领导还一条接一条的在问，为什么都还没有填。&nbsp;然后有一个同事在大群里面发了一条说"表格有问题，打不开，有催的功夫不如自己点开看看"之后领导就在群里发癫了&nbsp;今天早上到公司&nbsp;领导直接把同事叫到会议室，进去二话没说同事扇了自己好几个大嘴巴子，说都是我错了行吧，会议室是透明玻璃，隔音很好都能听到&nbsp;领导直接不敢说话，让同事回去了，还十分钟把表格改好发群里，说不着急下班交就行&nbsp;这位同事被我们所有人奉为永远的哥&nbsp;中午吃饭还和我们说发疯真的很爽，有一种我不过了，谁也别想活了的感觉，还说下次发疯直接扇领导
白烁：respect
打工人的精神状态
点赞 评论 收藏
分享
10-14 17:38
门头沟学院 软件测试
招聘软件也有薪资标题党了😅气急败坏的HR
vegetable_more_exercise：1-1.5万，没错啊，最少是1人民币，在区间内
点赞 评论 收藏
分享
10-27 17:26
东北大学 Java
点赞 评论 收藏
分享
11-23 11:04
门头沟学院 Java
双非二本java后端的“海市蜃楼”
前言：真的很折磨，投递4个月，boss沟通1200多家以及中大厂官网各种投简历，最后只有5面，已经累了，总算是在12月之前拿到一个满意的offer了。&nbsp;双非二本要是java后端起步太晚（大二下学期才开始）或者没有过硬的奖项和项目还是考虑转吧，我是大一开学就决定走java后端，当时天真的以为只要踏踏实实的就可以找到满意的offer，现在看来，有时候选择&gt;&gt;努力。以我投了4个月的心得来看在没有实习经历前中大厂基本不会给面试的机会，“9分运气1分实力”在此刻具象化了，在刚开始投简历的时候我也曾以为java后端都可以像牛客上的大佬人手至少一份大厂offer,未曾想时间击碎了这虚...
Astraia：就算是幸存者偏差之下的人也都没有一蹴而就的成功，一步一步往上爬吧，总不能失去做梦的勇气
双非有机会进大厂吗 找工作，你会甘心进小厂还是猛冲大厂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
229308次浏览 2025人参与
# ai智能作图 #
17948次浏览 234人参与
# 北方华创开奖 #
65449次浏览 545人参与
# 25届秋招总结 #
389486次浏览 3886人参与
# 硬件兄弟们 甩出你的华为奖状 #
77427次浏览 623人参与
# 地方国企笔面经互助 #
6350次浏览 15人参与
# 阿里云管培生offer #
56662次浏览 1726人参与
# 实习，投递多份简历没人回复怎么办 #
2432906次浏览 34685人参与
# 哪些公司校招卡第一学历 #
32138次浏览 99人参与
# 在职场上，你最讨厌什么样的同事 #
5447次浏览 78人参与
# 实习与准备秋招该如何平衡 #
721546次浏览 8539人参与
# 我的实习求职记录 #
6114449次浏览 83908人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
4569次浏览 46人参与
# 如果再来一次，你还会选择这个工作吗？ #
107209次浏览 1077人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9525次浏览 197人参与
# 实习想申请秋招offer，能不能argue薪资 #
35562次浏览 308人参与
# 牛客租房专区 #
4320次浏览 119人参与
# 腾讯求职进展汇总 #
206809次浏览 1693人参与
# 如果有时光机，你最想去到哪个年纪？ #
27358次浏览 567人参与
# 中兴求职进展汇总 #
467518次浏览 2436人参与
# 华为工作体验 #
109844次浏览 854人参与
# 还记得你第一次面试吗？ #
31069次浏览 438人参与
牛客网
牛客企业服务