Codeforces VK Cup 2017

Codeforces VK Cup 2017 - Round 2

2024-01-28 05:48

本文主要是介绍Codeforces VK Cup 2017 - Round 2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. Voltage Keepsake

二分答案。

B. Volatile Kite

把问题转换为求每个点到相邻2点组成的线段的距离。

C. Vulnerable Kerbals

这题有点意思。我们可以推出这样的结论，当前缀的积(mod m)与m互质时，添加一个数，前缀积可以转换为所有数；但是当前缀的积(mod m)与m的最大公约数为gcd时，添加一个数，只能转换为gcd的倍数。所以策略是先转化为与m的最大公约数小的，再转化为大的。。可以dfs求一下转化顺序，然后利用逆元来转化。

#include <bits/stdc++.h>using namespace std;#define ll long longconst int maxn = 200010;
int mod;  void ExEuclid(ll a,ll b,ll &x,ll &y,ll &q){      if(b==0){      x=1;y=0;q=a;      return;      }      ExEuclid(b,a%b,y,x,q);y-=x*(a/b);      
}      ll inv(ll num){ll x,y,q;      ExEuclid(num,mod,x,y,q);      return (x+mod)%mod;  
}int n,m;
vector<int> res;
bool vis[maxn];
int dp[maxn];
int nxFac[maxn];
vector<int> fac;int dfs(int mm){if(dp[mm] != -1){return dp[mm];}int div = m / mm;int ans = 0;for(int i=1;i<mm;i++){if(!vis[i*div] && (__gcd(i,mm) == 1) ){ans ++;}}int mx = 0;int mxnum = 0;for(int i=2;i<mm;i++){if(mm % i == 0){int tmp = dfs(mm/i);if(tmp > mx){mx = tmp;mxnum = i;}}}ans += mx;dp[mm] = ans;nxFac[mm] = mxnum;return ans;
}int main(){memset(dp,-1,sizeof(dp));cin>>n>>m;if(m==0){cout<<0<<endl;return 0;}mod = m;for(int i=0;i<n;i++){int a;scanf("%d",&a);vis[a] = 1;}dfs(m);int div = 1;int mm = m;fac.push_back(1);while(nxFac[mm]){fac.push_back(nxFac[mm]);mm /= nxFac[mm];}if(mm!=1){fac.push_back(mm);}int tmp = m;vector<int> order;vector<int> divs;divs.push_back(1);for(int x : fac){tmp /= x;div *= x;for(int i=1;i<=tmp;i++){int id = i*div;if(id == m){id = 0;}if(!vis[id] && __gcd(i,tmp)==1){order.push_back(id);divs.push_back(div);vis[id] = 1;}}}ll prod = 1;for(int i=0;i<(int)order.size();i++){assert(i!=m);prod /= divs[i];order[i] /= divs[i];mod /= divs[i];ll ans = (ll)order[i]*inv(prod);ans %= mod;mod *= divs[i];prod *= divs[i];prod *= ans;prod %= mod;res.push_back(ans);}cout<<res.size()<<endl;for(int x:res){printf("%d ",x);}return 0;
}