A. Choosing Ice Cream
题目大意：有n种冰淇淋和一个k面的骰子，问至少扔几次骰子使得选择每种骰子的概率相等。
先把大神的代码先放这，还没看懂当然也可以用快速幂试试
// Time complexity: O(log(n))
// Memory: O(1)// @EXPECTED_RESULTS@: CORRECT/* Solution method:** Insight: n divides k^t iff n divides d^t, where d = gcd(n,k).* Hence n divides k^t iff n/d divides d^(t-1).* Let n' = n/d, k' = d and t' = t-1. Then n divides k^t iff n' divides k'^t'.* We can repeat this process.* If at some point we have n' = 1, then t' = 0 is the smallest t';* t is then the number of iterations.* If it is not unbounded, we should eventually get t' = 0. Then n' = 1 must hold.* Hence, if we never reach n' = 1, it is unbounded.* We never reach n' = 1 iff at some point k' = 1 (and n' > 1).*/#include <algorithm>
#include <cstdio>
#include<iostream>
using namespace std;// Greatest common divisor
int gcd (int a, int b)
{ return b ? gcd(b, a%b) : a;
}int main()
{ int runs, run, n, k, t;scanf("%d", &runs);for (run = 0; run < runs; run++){scanf("%d %d", &n, &k);//cout<<"n="<<n<<",k="<<k<<endl;for (t = 0; n > 1 && k > 1; t++){//cout<<"***n="<<n<<",k="<<k<<endl;k = gcd(n, k);n /= k;}if (n > 1)printf("unbounded\n");elseprintf("%d\n", t);}return 0;
}
B. Failing Components
C. Floor Painting
D. Lift Problems
E. Pawns
F. Runway Planning
签到题
#include<iostream>
#include<cstdio>
using namespace std;
int main(){int t,n,ans;scanf("%d",&t);while(t--){scanf("%d",&n);if(n>180) n-=180;ans=(n+5)/10;if(ans==0) ans=18;printf("%02d\n",ans);}return 0;
}G. Spy Network
H. Talent Selection
I. Train Station Tunnel
J. Word Search
