【准备4】数学与数论

2022/2/15 6:13:41

编程Tag： return int long include 数学 ll 数论 准备 quad

本文主要是介绍【准备4】数学与数论，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

P1246 编码

Problem Link

solution

\(\quad\)先把位数比自己小的编码个数算出来，然后从左到右考虑位数和自己相等，但是比自己小的编码。这玩意和一般的字典序还不太一样，因为是升序，还要用组合数来计算。

code

#include<bits/stdc++.h>

using namespace std;
string s;
int ans, n;

int c(int m, int n) {
    if (m == 0)return 1;
    int a = 1;
    for (int i = n; i > n - m; i--) a *= i;
    for (int i = m; i > 1; i--) a /= i;
    return a;
}

int main() {
    cin >> s, n = s.size();
    for (int i = 1; i < n; i++)
        if (s[i] <= s[i - 1]) {
            cout << 0;
            return 0;
        }
    for (int i = 1; i < n; i++)ans += c(i, 26);
    for (int i = 0; i < n; i++)
        for (char j = (i == 0 ? 'a' : s[i - 1] + 1); j < s[i]; j++)
            ans += c(n - i - 1, 'z' - j);
    ans++;
    cout << ans;
    return 0;
}

P1069 [NOIP2009 普及组] 细胞分裂

Problem Link

solution

\(\quad\)能够满足条件的细胞的质因数一定包括 m1 的质因数，那么对 m1 先质因数分解，然后对于每一个细胞数都随便判断一下是否满足条件，然后统计一下答案就可以了。

code

#include <iostream>

using namespace std;
int n, m1, m2, s[10001], zs[10001] = {0}, mz, t = 2, c, ans = 0x7fffffff, l;

int main() {
    cin >> n >> m1 >> m2;
    for (int i = 1; i <= n; i++) cin >> s[i];
    if (m1 == 1) {
        cout << 0 << endl;
        return 0;
    }
    while (m1 != 1) {
        while (!(m1 % t)) m1 /= t, zs[t]++;
        mz = max(mz, t);
        zs[t++] *= m2;
    }

    for (int i = 1; i <= n; i++) {
        l = 0;
        for (int j = 2; j <= mz; j++) {
            if (!zs[j]) continue;
            c = 0;
            while (!(s[i] % j)) s[i] /= j, c++;
            if (!c) {
                l = 0x7fffffff;
                break;
            }
            l = max(l, (zs[j] - 1) / c);
        }
        ans = min(ans, l);
    }
    cout << (ans == 0x7fffffff ? -1 : ans + 1) << endl;
    return 0;
}

P2638 安全系统

Problem Link

solution

\(\quad\)这个题目的题意很有误导性，每一个存储空间可以放任意数量的 0 和 1，而不是只能放一个。我一开始理解错了，然后就推了个错的组合数。不过知道了正确的题意后这个题目还是很简单。首先我们要知道 0 和 1 是两个独立的类别，所以我们分开考虑，0 放几个，1 放几个。确定了两个类别的数量后就发现其实就是要求：对于 n 个盒子，有几种放 x 个小球的方案数，那么这玩意就可以用插板法去做就可以了。一个不算技巧的技巧就是先预处理好杨辉三角。

code

#include<iostream>
using namespace std;
int n,a,b;
unsigned long long P[51][51],ans;
void Work(int n){
    for(int i=0;i<=n;++i)P[i][0]=P[i][i]=1;
    for(int i=2;i<=n;++i)
        for(int j=1;j<=i;++j)
            P[i][j]=P[i-1][j]+P[i-1][j-1];
}
int main()
{
    cin>>n>>a>>b;
    Work(n+max(a,b));
    for(int i=0;i<=a;++i)
        for(int j=0;j<=b;++j)
            ans+=P[n+i-1][n-1]*P[n+j-1][n-1];
    cout<<ans;
    return 0;
}

P1835 素数密度

Problem Link

solution

\(\quad\)可以注意到区间长度其实是很短的，那么我们可以先预处理之前的一些质数，然后用线性筛的思想去筛，唯一要注意的就是 1 不是质数。
\(\quad\)其实我最开始的想法是对于每一个数用费马小定理去判断，复杂度大概是 \(O(nlogn)\) 不知道能不能过去。

code

略

P1072 [NOIP2009 提高组] Hankson 的趣味题

Problem Link

solution

\(\quad\)重点在于怎么控制这个范围。我们知道这个数字一定是 \(b_1\) 的因数，那么我们枚举 \(\sqrt b_1\) 的范围，然后判断是否满足条件即可。

code

#include<bits/stdc++.h>

using namespace std;

int gcd(int a, int b) {
    return (b == 0) ? a : gcd(b, a % b);
}

int main() {
    int T, ff;
    cin >> T;
    while (T--) {
        int a0, a1, b0, b1, ans = 0;
        cin >> a0 >> a1 >> b0 >> b1;
        int b = sqrt(b1);
        for (int i = 1; i <= b; i++) {
            if (b1 % i == 0) {
                if (i % a1 == 0 && gcd(i / a1, a0 / a1) == 1 && gcd(b1 / b0, b1 / i) == 1)
                    ans++;
                int y = b1 / i;
                if (i == y) continue;
                if (y % a1 == 0 && gcd(y / a1, a0 / a1) == 1 && gcd(b1 / b0, b1 / y) == 1) ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

P1403 [AHOI2005]约数研究

Problem Link

solution

\(\quad\)考虑每一个数的贡献，那么答案就是：

\[\sum_{i=1}^n \lfloor \frac{n}{i}\rfloor \]

\(\quad\)这玩意可以用数论分块优化一下

code

int T,n,ans;

inline void solve(){
    n=read();
    for(int l=1,r=0;l<=n;l=r+1){
        r=n/(n/l);
        ans+=(n/l)*(r-l+1);
    }
    printf("%d",ans);
}

P3383 【模板】线性筛素数

Problem Link

solution

\(\quad\)略

code

#include <cstdio>
#include <cstring>

bool isPrime[100000010];
//isPrime[i] == 1表示：i是素数
int Prime[6000010], cnt = 0;
//Prime存质数

void GetPrime(int n)//筛到n
{
	memset(isPrime, 1, sizeof(isPrime));
	//以“每个数都是素数”为初始状态，逐个删去
	isPrime[1] = 0;//1不是素数
	
	for(int i = 2; i <= n; i++)
	{
		if(isPrime[i])//没筛掉 
			Prime[++cnt] = i; //i成为下一个素数
			
		for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) 
		{
        	//从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
            //当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
			isPrime[i*Prime[j]] = 0;
            
			if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
				break; //重要步骤。见原理
		}
	}
}

int main()
{
	int n, q;
	scanf("%d %d", &n, &q);
	GetPrime(n);
	while (q--)
	{
		int k;
		scanf("%d", &k);
		printf("%d\n", Prime[k]);
	}
	return 0;
}

P1226 【模板】快速幂||取余运算

Problem Link

solution

\(\quad\)略

code

#include<iostream>
using namespace std;
long long b,p;
int k;
long long ksm(long long b,long long p,int k)
{
    long long res=1;
    if(p==0) return 1%k;
    while(p!=0)
    {
        if(p%2==1) res*=b;
        b*=b;
        p/=2;
        res%=k;
        b%=k;
    }
    return res;
}
int main()
{
    cin>>b>>p>>k;
    cout<<b<<'^'<<p<<' '<<"mod"<<' '<<k<<'='<<ksm(b,p,k);
    return 0;
}

P1075 [NOIP2012 普及组] 质因数分解

Problem Link

solution

\(\quad\)正常的想法就是以开根的范围去枚举，但事实如果你特别闲，打个 \(Pollard\space - \space rho\) 也是可以的。

code

#include<bits/stdc++.h>

#define ll long long
#define lll __int128
using namespace std;
ll max_factor, n;

inline ll gcd(ll a, ll b) {
    return (b == 0) ? a : gcd(b, a % b);
}

inline ll ksm(ll x, ll p, ll mod) {
    ll ans = 1;
    while (p) {
        if (p & 1) {
            ans = (lll) ans * x % mod;
        }
        x = (lll) x * x % mod;
        p >>= 1;
    }
    return ans;
}

inline bool mr(ll x, ll b) {
    ll k = x - 1;
    while (k)//如果能继续说明上次模数一定为1，那么下一次模数一定为正负1 
    {
        ll cur = ksm(b, k, x);//b的k次方%x 
        if (cur != 1 && cur != x - 1) return 0;//不为1或x-1 
        if ((k & 1) == 1 || cur == x - 1) return 1;//k为奇数（无法继续）或 cur=x-1就认定是质数 
        k >>= 1;//开根，为下一次的平方，二次探测定理 
    }
    return 1;
}

inline bool prime(ll x) {
    if (x < 2 || x == 46856248255981ll) return 0;
    if (x == 2 || x == 3 || x == 5 || x == 7 || x == 61 || x == 24251) return 1;
    return mr(x, 2) && mr(x, 61);
}

inline ll f(ll x, ll c, ll n) {
    return ((lll) x * x + c) % n;
}

inline ll pr(ll x) {
    ll s = 0, t = 0, c = 1ll * rand() % (x - 1) + 1;
    ll val = 1;
    for (int i = 1;; i <<= 1, s = t, val = 1) {
        for (int j = 1; j <= i; j++) {
            t = f(t, c, x);
            val = (lll) val * abs(t - s) % x;
            if ((j % 127) == 0) {
                ll d = gcd(val, x);
                if (d > 1) return d;
            }
        }
        ll d = gcd(val, x);
        if (d > 1) return d;
    }
}

inline void fac(ll x) {
    if (x <= max_factor || x < 2) return;
    if (prime(x)) {
        max_factor = max_factor > x ? max_factor : x;
        return;
    }
    ll p = x;
    while (p >= x) p = pr(x);
    while ((x % p) == 0) x /= p;
    fac(x), fac(p);
}

int main() {
    int T;
    srand((unsigned) time(NULL));
    ll n;
    cin >> n;
    max_factor = 0;
    fac(n);
    printf("%lld\n", max_factor);
    return 0;
}

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

Problem Link

solution

\[P=x\times x_0,Q=y\times x_0,gcd(x,y)=1 \]

\[LCM=y_0=x\times y\times x_0 \]

\[\frac{y_0}{x_0}=x\times y,gcd(x,y)=1 \]

\(\quad\)那么对于上述式子求出有几对数字就可以了

code

int T,n,ans,x0,y;

inline void solve(){
    x0=read();y=read();
    if(y%x0) return puts("0"),void();
    n=y/x0;
    FOR(i,1,n){
        if(n%i==0 && __gcd(i,n/i)==1) {++ans;}
    }
    printf("%d\n",ans);
}

P2926 [USACO08DEC]Patting Heads S

Problem Link

solution

\(\quad\)类似于线性筛的思想从小到大筛就可以了，因为数是两两不相同，可以证明复杂度是正确的。

code

#include<bits/stdc++.h>
using namespace std;
int a[10000005];
int n,mx=-100;
int b[10000005];
int cnt[10000005];
void get_factor(){
    for (int i = 1;  i <= 10000000; i++){
    	if(!b[i]) continue;
    	for (int j = 1; j <= 10000000 / i; j++){
    		 if(b[i*j]) cnt[i*j]+=b[i];
    		 if(i*j==i) cnt[i]--;
        }   	
    } 
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[a[i]]++;
    }
    get_factor();
    for(int i=1;i<=n;i++)
        cout<<cnt[a[i]]<<endl;
}

P3913 车的攻击

Problem Link

solution

\(\quad\)一个容斥 + 组合数学

code

#include <bits/stdc++.h>
#define ll long long
const int maxn=1e6+5;
using namespace std;
ll n,k;
ll x[maxn],y[maxn];
int main(){
        scanf("%lld%lld",&n,&k);
        for(ll i=0;i<k;i++){
                //cin>>x[i]>>y[i];
            scanf("%lld%lld",&x[i],&y[i]);
        }
        sort(x,x+k);
        sort(y,y+k);
        ll sizex=unique(x,x+k)-x;
        ll sizey=unique(y,y+k)-y;
        printf("%lld",n*n-(n-sizex)*(n-sizey));
        return 0;
}

P1017 [NOIP2000 提高组] 进制转换

Problem Link

solution

\(\quad\)其实仿照正整数的求进制就可以了。就有一点要注意下：-15%-2=-1,-2*7-1=-15 ，但是我们需要让 15%-2=1,-2*8+1=-15，这种情况就需要特殊处理一下。

code

int T,n,base;
char zhb[20]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};

inline void change(int n,int m){
    if(!n) return ;
    if(n>0) {change(n/m,m);cout<<zhb[n%m];}
    else if(n%m==0) {change(n/m,m);cout<<0;}
    else {change((n+1)/m+1,m);cout<<zhb[(n-((n+1)/m+1)*m)];}
}

P2789 直线交点数

Problem Link

solution

\(\quad\)我们不需要考虑每条直线具体在什么位置，而是需要考虑它们相对的平行与相交。假设已经确定了直线的个数，那么我们枚举平行的线段的个数，假设剩下的线段都不和这些线段平行，那么我们算出剩下的线段和平行的线段的交点数，再递归求解剩下的线段的交点数即可。

code

#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
int n,MAX=-1,ans=0;
bool f[11000];
void g(int n,int k)
{
        if (n==0) {f[k]=true;MAX=max(k,MAX);}
        else for (int r=n;r>=1;r--)g(n-r,r*(n-r)+k);
}
int main()
{
        cin>>n;
        memset(f,false,sizeof(f));
        g(n,0);
        for (int i=0;i<=MAX;i++)
                if (f[i]) ans++;
    cout<<ans;
        return 0;
}

P2822 [NOIP2016 提高组] 组合数问题

Problem Link

solution

\(\quad\)你可以把这个当作组合数意义下的递推，或者直接看作一个杨辉三角，不过这都无所谓，重要的就是预处理出所有的组合数，然后直接查询。

code

#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,k) for(register int i=j;i<=k;i++)
#define rep(i,j,k) for(register int i=j;i>=k;i--)
#define lid id<<1
#define rid id<<1|1
#define db double
using namespace std;
int t,m,k,n;
ll f[2002][2002],flag[2002][2002];
void yh()
{
	f[0][0]=f[1][0]=f[1][1]=1;
	fo(i,2,2001)
	{
		f[i][0]=1;
		fo(j,1,i)
		{
			f[i][j]=(f[i-1][j-1]%k+f[i-1][j]%k)%k;
			flag[i][j]=flag[i-1][j]+flag[i][j-1]-flag[i-1][j-1];
			if(f[i][j]==0) flag[i][j]++;
		}
		flag[i][i+1]=flag[i][i];
	}
}
int main()
{
	scanf("%d%d",&t,&k);
	yh();
	while(t--)
	{
		scanf("%d%d",&n,&m);
		if(n<m) printf("%d\n",flag[n][n]);
		else printf("%d\n",flag[n][m]);
	}
	return 0;
}

P1100 高低位交换

Problem Link

solution

\(\quad\)左/右边 16 位分别考虑一下就可以了

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;
    cin>>n;
    int x=pow(2,15);
    if(n>=x){
        int a1=n>>16;
        cout<<(((n-(a1<<16))<<16)+(a1))<<endl;
    }else{
        cout<<(n<<16)<<endl;
    }
    return 0;
}

P1866 编号

Problem Link

solution

\(\quad\)排序一下，然后就是基础的组合数学

code

#include<iostream>
#include<algorithm>
using namespace std;
int n,j,i,a[55];
long long t;
int main()
{
    cin>>n;
    t=1;j=0;
    for(i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    for(i=0;i<n;i++)
    {
        t=t*(a[i]-j);
        t%=1000000007;
        j++;
    }
    cout<<t<<endl;
    return 0;
}

P1469 找筷子

Problem Link

solution

\(\quad\)可以以十进制作中转站去转

code

#include<iostream>
#include<cmath>

using namespace std;
int n, m, l, i, p, d, a[500];
long long h;
string s;

int main() {
    cin >> n >> s >> m;
    p = 0;
    l = s.size();
    h = 0;
    if (n <= 10) {
        for (i = 0; i < l; i++) {
            h += pow(n, i) * (s[l - i - 1] - '0');

        }
    } else {
        for (i = 0; i < l; i++) {
            if (s[l - i - 1] >= 'A' && s[l - i - 1] <= 'Z') { h += pow(n, i) * (s[l - i - 1] - 'A' + 10); }

            else { h += pow(n, i) * (s[l - i - 1] - '0'); }

        }

    }
    while (h != 0) {

        a[p] = h % m;
        p++;
        h = h / m;
    }
    for (d = p - 1; d >= 0; d--) {
        if (a[d] < 10) cout << a[d];
        else if (a[d] == 10) cout << 'A';
        else if (a[d] == 11) cout << 'B';
        else if (a[d] == 12) cout << 'C';
        else if (a[d] == 13) cout << 'D';
        else if (a[d] == 14) cout << 'E';
        else if (a[d] == 15) cout << 'F';

    }

    return 0;
}

P1469 找筷子

Problem Link

solution

\(\quad\)全部异或一下落单的就是最后的答案

code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,ans;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        ans^=x;
    }
    cout<<ans;
    return 0;
}


这篇关于【准备4】数学与数论的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程