CSP赛前集训【次芝麻】

次芝麻

题目描述：（暂不提供）

这道题考场写了一个找寻环节的暴力。然后很高兴的拿到里60’。 贴一个考场代码：

#include <cstdio> #include <cstring> #include <tr1/unordered_map> using namespace std; typedef long long ll; const ll N = 1000010; tr1::unordered_map<long long,tr1::unordered_map<long long,int> > vis; inline ll min(ll a,ll b) { return a < b ? a : b; } ll n,m,k; ll a[N][2],cnt; int main() { freopen("sesame.in","r",stdin); freopen("sesame.out","w",stdout);l scanf("%lld%lld%lld",&n,&m,&k); for(;!vis.count(n) || (vis.count(n) && !vis.count(m)) && cnt <= k;) { cnt++; a[cnt][0] = n, a[cnt][1] = m, vis[n][m] = cnt; vis[m][n] = cnt; if(n < m) m = m - n, n = 2 * n; else n = n - m, m = 2 * m; if(cnt == k) { printf("%lld",min(n,m)); return 0; } if(!n || !m) { printf("0"); return 0;} } ll p = cnt + 1 - vis[n][m],g = vis[n][m] - 1; k = (k - g) % p; printf("%lld\n",min(a[vis[n][m] + k][1],a[vis[n][m] + k][0])); fclose(stdin); fclose(stdout); return 0; }

其实正解很简单。 假设每一轮小的数为$x$，大的数为$y$。 那么下一轮$x$为$2x$，$y$为$y-x$。 在$mod(n+m)$的意义下$y-x$也等于$2y$ 然后我们就可以跑一个快速幂$AC$了。

#include <cstdio> #include <cstring> using namespace std; typedef long long ll; inline ll min(ll a,ll b) { return a < b ? a : b; } ll n,m,k,mod; ll f_pow(ll a,ll x) { ll ret = 1; for(;x;x >>= 1) (x & 1) && (ret = ret * a % mod), a = a * a % mod; return ret; } int main() { freopen("sesame.in","r",stdin); freopen("sesame.out","w",stdout); scanf("%lld%lld%lld",&n,&m,&k); mod = n + m; printf("%lld",min(n * f_pow(2,k) % mod,m * f_pow(2,k) % mod)); fclose(stdin); fclose(stdout); return 0; }

考场被$Z$某带节奏，整个机房包括$ZJJ$都在打寻环节找规律。然后竟然没有一个人考场$AC$？看来还是要冷静啊。