感觉这一场的复杂度非常的玄学... 也可能是我偷懒太长时间变菜了QAQ. C 题意: 给出 \(x,n\) ,求x质因子的从1到n的g(i,p)的连乘 思路: 求出x的每个质因子,直接连乘到n计算即可. #includebits/s
感觉这一场的复杂度非常的玄学... 也可能是我偷懒太长时间变菜了QAQ.
C
- 题意: 给出\(x,n\),求x质因子的从1到n的g(i,p)的连乘
- 思路: 求出x的每个质因子,直接连乘到n计算即可.
#include<bits/stdc++.h> #define ll long long using namespace std; typedef pair<int,int> pii; typedef vector<int> VI; vector<int> prime; const int MOD = 1e9+7; void get(ll x){ for(int i=2;i*i<=x;++i){ if(x%i==0){ prime.push_back(i); while(x%i==0) x/=i; } } if(x!=1) prime.push_back(x); } 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; } const int N = 1e5+10; int cnt[N]; int main(){ ll x,n; ll ans = 1; cin >> x >> n; get(x); for(auto p:prime){ ll res = 1; while(res<=n/p){ res*=p; ans = ans * qpow(p,n/res)%MOD; // 不是res的n/res次方 而是 p的n/res次方 这样可以避免乘过之后影响前面 } } ll t = (ll)ans; cout << t << endl; }
比赛时一直在想怎么容斥,让p乘过以后不会影响到前面,但看别人代码发现并不需要容斥,直接还用p做底就可以
D
- 题意: 给出一个图,让你把这个图三分(类比二分图).
- 思路: 暴力分,但分完要检查条件. 1.随便选一个没被染色的点u染色,若v与u没有边,且v没被染色过,则将v染成u的颜色.
2.重复1 三次. 3.判断所有点都被染色,且三种颜色都存在. 4.判断m(边数) == |col1|*|col2|+|col1|* |col3| + |col2|*|col3|,因为不同集合直接每个点都要存在边. 5.判断不同集合的两个点是否存在边
#include<bits/stdc++.h> #define ll long long using namespace std; typedef pair<int,int> pii; typedef vector<int> VI; const int N = 1e5+10; vector<int> G[N]; int head[N],tot; int cnt[4]; vector<int> block[4]; int color[N]; void add(int u,int v){G[u].push_back(v);} int n,m; int main(){ scanf("%d%d",&n,&m); int u,v; for(int i=1;i<=m;++i){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(int col = 1;col<=3;++col){ int idx = 0; for(int i=1;i<=n;++i) if(color[i]==0){idx = i;break;} if(idx ==0){ color[1] = 0; break; } color[idx] = col; for(auto v:G[idx]){ if(!color[v]) color[v] = -1; } for(int i=1;i<=n;++i){ if(color[i]==0) color[i] = col; if(color[i]==-1) color[i] = 0; } } for(int i=1;i<=n;++i){ cnt[color[i]]++; block[color[i]].push_back(i); } int sign = 0; if(cnt[0] || !cnt[1] || !cnt[2] || !cnt[3] || m!= cnt[1]*cnt[2] + cnt[2]*cnt[3] + cnt[1]*cnt[3]){ sign = 1; } for(auto u:block[1]){ sort(G[u].begin(),G[u].end()); for(auto v:block[2]){ auto it = lower_bound(G[u].begin(),G[u].end(),v); if(it == G[u].end() || *it!=v) sign = 1; } for(auto v:block[3]){ auto it = lower_bound(G[u].begin(),G[u].end(),v); if(it == G[u].end() || *it!=v) sign = 1; } } for(auto u:block[2]){ sort(G[u].begin(),G[u].end()); for(auto v:block[3]){ auto it = lower_bound(G[u].begin(),G[u].end(),v); if(it == G[u].end() || *it!=v) sign = 1; } } if(sign){ puts("-1"); return 0 ; } for(int i=1;i<=n;++i){ printf("%d ",color[i]); } puts(""); return 0; }
感觉4和5的判断是重复的,而且判断5居然不超时