数论复习c++

改造序列

题目描述

给定长度为$n$的序列$a_1,a_2,...,a_n$，你可以从中删除一些数，使得删完以后的序列中，所有相邻元素之和均为偶数。请问最少需要删除多少个数？

输入格式

第一行一个整数$T$，表示测试数据组数$T$

接下来$T$组数据，每组数据第一行一个整数$n$，第二行$n$个整数，空格分开

输出格式

$T$行，每行一个整数，表示相应数据的答案

样例 #1

样例输入 #1

2
5
2 4 3 6 8
6
3 5 9 7 1 3

样例输出 #1

1
0

提示

记$\sum n$为一个数据点中所有$n$之和

对于$100\%$的数据，$1⩽T⩽100$，$3⩽n⩽10^5$，$1⩽a_i⩽10^9$，$1⩽\sum n⩽10^5$

这道题很简单，只需要判断奇数和偶数的的个数，输出最小的那个数就行了，核心代码如下：

while(t--)
{int n,ansa=0,ansb=0;	//一定要附初值，不然后面的值不对for(int i=1;i<=n;i++){cin>>a[i];if(a[i]%2==0)	//判断奇数偶数的个数{ansa++;}else{ansb++;}/*这里也个可以怎么写：int x;cin>>x;if(x%2==0){ansa++;}else{ansb++;}*/}printf("%d\n",min(ansa,ansb));
}

非倍数求和

题目描述

给定$n,a,b$，求$1$至$n$之间所有既不是$a$的倍数也不是$b$的倍数的数之和。

输入格式

一行，三个整数$n,a,b$

输出格式

一行，一个整数，表示答案

样例 #1

样例输入 #1

10 3 5

样例输出 #1

22

提示

对于$30\%$的数据，$1\leqslant n,a,b\leqslant 10^3 $

对于$60\%$的数据，$1⩽n,a,b⩽10^6$

对于$100\%$的数据，$1⩽n,a,b⩽10^9$

这道题是一道典型的数论题，代码如下：

#include <bits/stdc++.h>
using namespace std;
long long gcd(int a,int b)
{if(b==0){return a;}return gcd(b,a%b);
}
long long lcm(int a,int b)
{return (long long)a*b/gcd(a,b);/*这道题也可以怎么写:return (long long)a*b/__gcd(a,b);这是直接调用库里的gcd手写的gcd表示：那我走*/
}
int main()
{long long n,a,b,ans=0,tota,totb,tott,t;scanf("%lld%lld%lld",&n,&a,&b);ans=(long long)(1+n)*n/2;	//高斯求和tota=(long long)(a+n/a*a)*(n/a)/2;totb=(long long)(b+n/b*b)*(n/b)/2;t=lcm(a,b);tott=(t+n/t*t)*(n/t)/2;printf("%lld",ans-tota-totb+tott);	//全部-a的倍数-b的倍数+a和b的倍数（这里因为a和b的倍数剪了两遍，所以要把那一遍加回来）return 0;
}

三数不同

题目描述

给定长度为$n$的序列$a_i$，请计算所有满足以下条件的三元组$(i,j,k)$的个数

• $i<j<k$
• $a_i$、$a_j$和$a_k$互不相同

输入格式

第一行，一个整数$n$

第二行$n$个整数$a_i$

输出格式

一个整数，表示答案

样例 #1

样例输入 #1

4
3 1 4 1

样例输出 #1

2

提示

对于$30\%$的数据，$n⩽2\times 100$，$a_i\leqslant 2\times 100 $

对于$60\%$的数据，$n⩽2\times 10^3$，$a_i⩽2\times 10^3$

对于$100\%$的数据，$3⩽n⩽2\times 10^5$，$1⩽a_i⩽2\times 10^5$

这道题是要找出有多少对 三元组 ，这道题的代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=2e6;
int h[N+10];
long long c(int n,int m)	//查找函数
{if(m==2){return (long long)n*(n-1)/2;}else if(m==3){return (long long)n*(n-1)*(n-2)/6;}
}
int main()
{int n,ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);h[x]++;}long long tot=c(n,3);	//找zzz的情况for(int i=1;i<=N;i++){if(h[i]>=2){tot-=c(h[i],2)*(n-h[i]);	//找zzy的情况，前两个找到了，最后一个随便找一个就行了}if(h[i]>=3){tot-=c(h[i],3);	//找zzz的情况}}printf("%lld",tot);return 0;
}