C:结论题：设n=k*p1+r=a*p2+b，只要n有两个及以上质因子，那么必然可以用第一个质因子表示出第二个质因子，所以答案是1
反之显然是其最小质因子
/* 1 2 3 4 1 3 2 4 n的所有因子 */ #include<bits/stdc++.h> using namespace std; #define ll long long #define N 1000006 ll n; bool vis[N]; ll prime[N],m; void init(){ for(int i=2;i<=1000000;i++){ if(!vis[i])prime[++m]=i; for(int j=1;j<=m;j++){ if(prime[j]*i>1000000)break; vis[prime[j]*i]=1; if(i%prime[j]==0)break; } } } ll p[N],mm; void divide(ll x){ mm=0; for(int i=1;i<=m;i++)if(x%prime[i]==0){ p[++mm]=prime[i]; while(x%prime[i]==0) x/=prime[i]; }/* puts("1"); cout<<x<<‘\n‘; */if(x>1) p[++mm]=x; } int main(){ init(); cin>>n; divide(n); if(mm==1 && p[1]==n){ cout<<n<<‘\n‘; } else if(mm==1 && p[1]!=n){ cout<<p[1]<<‘\n‘; } else cout<<1<<‘\n‘; } /* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 4 7 10 13 16 19 2 5 8 11 14 17 20 3 6 9 12 15 18 21 1 6 11 16 21 26 31 2 7 12 3 8 13 4 9 14 5 10 15 */
D:求补图联通块模板题
/* 这题可以转化为在补图上求出联通块的个数 每个点和其不相邻的点在补图上形成联通块 那么在补图上进行bfs求联通块： 1.所有点形成一个链表list，初始化一个队列que 2.如果que为空，说明新找到了一个联通块，则从链表头取出一个元素，同时删除该元素，反之从que中取出首元素 3.标记和当前元素cur相邻的所有点，然后遍历一次链表，将链表中未被标记的点加入que，同时从链表中删除 4.重复以上步骤直到 que和list皆为空 复杂度分析：每个结点只在链表中被删除一次， 每次标记完cur的相邻点并删除完链表后，链表中剩下的元素不会超过cur的度数，所以多次遍历链表的复杂度总和也是O(m) */ #include<bits/stdc++.h> #include<vector> using namespace std; #define ll long long #define N 200005 vector<int>G[N]; int n,m,ans; struct List{int pre,nxt;}l[N]; void del(int p){ l[l[p].nxt].pre=l[p].pre; l[l[p].pre].nxt=l[p].nxt; } int vis1[N],vis2[N];//点i是否在链表里，点i是否与当前点相邻 void bfs(){ queue<int>q; while(q.size())q.pop(); while(l[0].nxt!=n+1){ if(!q.size()){ int cur=l[0].nxt; del(l[0].nxt); vis1[cur]=1; q.push(cur); ans++; } while(q.size()){ int cur=q.front();q.pop(); for(auto x:G[cur])vis2[x]=1; int p=l[0].nxt; while(p!=n+1){ if(!vis2[p] && !vis1[p]){ q.push(p); del(p); vis1[p]=1; } p=l[p].nxt; } for(auto x:G[cur])vis2[x]=0; } } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } //初始化链表 for(int i=1;i<=n;i++) l[i].pre=i-1,l[i].nxt=i+1; l[0].nxt=1;l[n+1].pre=n; bfs(); cout<<ans-1<<‘\n‘; }
E.图论求环+状态压缩dp：枚举子集O(3^n)讨论
自己写了半天没写出来。。感觉极其繁琐，贴了做法。待补
/*
先求出每堆的目标值X 对于第i堆，我们扔掉元素a[i][j],那么需要的元素就是X-(sumi-a[i][j]) 假设这个元素的位置是a[x][y]，那么我们从a[x][y]到a[i][j]连一条边 那么这个图上会出现一些环，由于每个数都不同，所以一个环最多经过一堆一次 要求找出一些环，使这些环刚好覆盖k堆一次 先tarjan找环，每个环记录覆盖的堆序号,元素的下标，然后状态压缩dp 枚举所有环， dp[S]表示 当前已经覆盖的状态是S，pre[S]表示S状态是从哪个环转移来的 这个状压dp是经典的O(3^n)的子集状压dp，枚举dp[S]的所有子集S‘,如果有对应S‘的环且dp[S-S‘]是可行解，那么dp[S]可行 预处理S的所有子集，id[S]表示覆盖状态S的环序号，这样能保证每个环不冲突
*/
原文：https://www.cnblogs.com/zsben991126/p/11817226.html
