题目点这里 #include<iostream> #include<algorithm> #include<string.h> using namespace std; const int N=200010; int e[N],h[N],idx,ne[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int n,m; bool st[N]; int ans=0x3f3f3f3f; int dfs(int u)//该点的所有子节点边数 { st...

题目点这里 #include<iostream> #include<string.h> #include<queue> using namespace std; const int N=100010; int h[N],e[N],idx,ne[N]; int d[N]; int n,m; bool st[N]; int bfs() { memset(d,0x3f,sizeof(d)); d[1]=0; queue<int>q; q.push(1); st[1]=1; while(q.si...

题目点这里 #include<iostream> #include<algorithm> #include<vector> using namespace std; int n,m; typedef pair<int,int> PII; vector<PII> add,query; vector<int> alls; const int N=300010; int a[N],s[N]; int find(int x) { return lower_bound(alls.begin(),alls.e...

容器类型<容器里放的类型>::iterator 给他取个名字~it 遍历的时候 for(it=容器名.begin();it!=容器名.end();it++) { (*it)才代表取里面的值 } 手写vector去重函数 vector<int>::iterator unique(vector<int>&a) { int j=0; for(int i=0;i<alls.size();i++) { while(!i||a[i]!=a[i-1]) a[j++]=a[i]; } return alls....

题目在这里 #include<iostream> using namespace std; int gcd(int a,int b) { return b?gcd(b,a%b):a; } int main() { int n; cin>>n; while(n--) { int a,b; cin>>a>>b; printf("%d\n",gcd(a,b)); } return 0; }

欧拉函数主要是用来算互质数个数的。 公式就是结论：ϕ(N)表示1 N中与N互质的数的个数结论：ϕ(N)表示1 N中与N互质的数的个数 N=p1a1×p2a2×……×p2a2N=p1a1×p2a2×……×p2a2 ϕ(N)=N(1−1p1)(1−1p2)……(1−1pn)ϕ(N)=N(1−1p1)(1−1p2)……(1−1pn) =∏ni=1piai=∏i=1npiai 求一个数的复杂度：求一个数的复杂度：n√ 题目 #include<iostream> using namespace std; int n; int main() { cin>>n; ...

题目 #include<iostream> using namespace std; const int N=1000010; bool st[N]; int prime[N]; int ph[N]; int cnt; long long ola(int n) { ph[1]=1; for(int i=2;i<=n;i++) { if(!st[i]) { prime[cnt++]=i; ph[i]=i-1; } ...

时间复杂度 log k 题目 #include<iostream> using namespace std; typedef long long LL; LL qs(int a,int b,int mod) { long long res=1; while(b) { if(b&1) res=res*a%mod; b>>=1; a=(long long) a*a%mod; } return res; } int main() { int n; ...

当n为质数时，可以用快速幂求逆元： a / b ≡ a * x (mod n) 两边同乘b可得 a ≡ a * b * x (mod n) 即 1 ≡ b * x (mod n) 同 b * x ≡ 1 (mod n) 由费马小定理可知，当n为质数时 b ^ (n - 1) ≡ 1 (mod n) 拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n) 故当n为质数时，b的乘法逆元 x = b ^ (n - 2) 当n不是质数时，可以用扩展欧几里得算法求逆元： a有逆元的充要条件是a与p互质，所以gcd(a, p) = 1 假设a的逆元为x，那么有a * x ≡ 1 (m...

题目 #include<iostream> using namespace std; int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return a; } int d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } int main() { int n; cin>>n; while(n--) { ...

题目 思路就是先从c列开始找出最大的一行与目前第r行做交换，然后把该行的第一个数除成1，再把r行下面的第c个元素消成0。如果最后r比n小，有无解和无限解的可能，等式左边已经变成0了，如果右边不为0就是无解，另外的就是有无限解。 #include<iostream> #include<algorithm> #include<cmath> using namespace std; const int N=110; const double eps=1e-6; double a[N][N]; int n; int gauss() { int...

题目 第一种：复杂度为n*n #include<iostream> using namespace std; const int N=2010; int c[N][N]; const int mod=1e9+7; void init() { for(int i=0;i<N;i++) for(int j=0;j<=i;j++) if(!j) c[i][j]=1; else c[i][j]=(long long)(c[i-1][j]+c[i-1][j-1])%mod; } int main() { i...

题目 题意大致是输入2的64次方以内的数求出它们取模以后下标的斐波那契数列的值，斐波那契数列在模上某个值后是具有循环节的，我们要把循环节的长度算出来，然后把循环节长度带入快速幂最后再模上n求出答案。本题坑点就是数据范围用longlong还不够要用unsigned long long，当n为1的时候答案都是0。 AC代码： #include<iostream> using namespace std; typedef unsigned long long ull; const int N=1010000; int f[N]; int qs(ull a,ull b,int n) { ...

题目 题目就是求出两个大组合数的比值，精度保留小数点后五位。用分解质因数做 #include<iostream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int num[100010]; void cal(int d,int flag) { if(flag) { for(int i=2;i<=d;i++) { while(d%i==0) { num[i]++; d/=i...