题解
问题A
思路：用视频中讲的模板，套模版。。
#include<iostream>
using namespace std;
typedef long long int ll;
int mypoww(ll x, ll y) {
ll ans = 1, y1 = y,x1=x;
while(y1) {
if (y1 & 1)ans = ans * x1%y;
x1 = x1 * x1%y;
y1 >>= 1;
}
if (x == ans)return 1;
else return 0;
}
int isprime(ll y) {
for (int i = 2; i * i <= y; i++) {
if (y % i == 0)return 0;
}
return 1;
}
int main()
{
ll x, y;
cin >> y >> x;
while (x != 0 && y != 0) {
if (isprime(y)==1) {
cout << "no" << endl;
}
else {
if (mypoww(x, y)==1)cout << "yes" << endl;
else cout << "no" << endl;
}
cin >> y >> x;
}
}
问题B
思路：可以一次求mod最后相加在求mod，其他的依然是套模版
代码
#include<iostream>
using namespace std;
typedef long long int ll;
int mypoww(ll x, ll y) {
ll ans = 1, y1 = y,x1=x;
while(y1) {
if (y1 & 1)ans = ans * x1%y;
x1 = x1 * x1%y;
y1 >>= 1;
}
if (x == ans)return 1;
else return 0;
}
int isprime(ll y) {
for (int i = 2; i * i <= y; i++) {
if (y % i == 0)return 0;
}
return 1;
}
int main()
{
ll x, y;
cin >> y >> x;
while (x != 0 && y != 0) {
if (isprime(y)==1) {
cout << "no" << endl;
}
else {
if (mypoww(x, y)==1)cout << "yes" << endl;
else cout << "no" << endl;
}
cin >> y >> x;
}
}
问题C
思路：注意提给条件，还有1000000007，我给忽略了第一次，，还是套路，套模版
#include<iostream>
using namespace std;
typedef long long int ll;
int mypoww(ll x, ll y,ll mod) {
ll ans = 1;
while(y) {
if (y & 1)ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
int main()
{
ll num, x, y, mod;
cin >> num;
while (num--)
{
ll times, ans = 0;
cin >> mod >> times;
for (ll i = 1; i <= times; i++) {
cin >> x >> y;
ans += mypoww(x, y, mod);
}
ans %= mod;
cout << ans << endl;
}
}
问题D
思路：这道题数据看完后，我用的数组进行了统计，，只不太大，就后边暴力过了..
#include<iostream>
#include<cstdio>
using namespace std;
int ar[10001];
int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
memset(ar, 0, sizeof(ar));
int max = 0;
for (int i = 1; i <= n; i++) {
int a;
scanf("%d", &a);
ar[a]++;
max = max < a ? a : max;
}
int flag = -1;
for (int i = 1; i <= max; i++) {
if (ar[i] > n / 2) {
flag = i;
break;
}
}
cout << flag << endl;
}
}
例题E
思路：这道题好像没啥可说的，，直接模板了
#include<iostream>
using namespace std;
typedef long long int ll;
int mypoww(ll x, ll y, ll mod) {
ll ans = 1;
while (y) {
if (y & 1)ans = ans * x % 10;
x = x * x % 10;
y >>= 1;
}
return ans;
}
int main()
{
int num;
cin >> num;
while (num--)
{
ll x;
cin >> x;
cout << mypoww(x, x, 10) << endl;
}
}
例题F
思路：课堂上讲的例题，没啥说的..
#include<iostream>
using namespace std;
typedef long long int ll;
ll mypoww(ll x, ll y, ll mod) {
ll ans = 1;
while (y) {
if (y & 1)ans = ans * x % mod;
x = (x * x)%mod;
y >>= 1;
}
return ans;
}
int main()
{
ll a, b;
cin >> a >> b;
while (a != 0 && b != 0)
{
cout << mypoww(a, b, 1000) << '\n';
cin >> a >> b;
}
}
例题G
思路:这道题首先从找末尾0个数转化为2，5的对数，因2明显多于5，就最终转化为找多少个5，找一个数符合条件适合用二分..
#include<iostream>
using namespace std;
typedef long long int ll;
ll myf(ll n) {
ll ans = 0;
while (n) {
ans += n / 5;
n /= 5;
}
return ans;
}
int main()
{
int num;
cin >> num;
int i = 1;
while (i<=num)
{
ll q;
cin >> q;
ll rights = 2000000000, lefts = 0, mid;
while (lefts <= rights)
{
mid = (rights + lefts) / 2;
if (myf(mid) < q)lefts = mid + 1;
else rights = mid - 1;
}
if (q == myf(lefts)) {
printf("Case %d: %lld\n", i, lefts);
}
else printf("Case %d: impossible\n", i);
i++;
}
}
例题H
思路：这道题的难点之精度，如左值和右值间差多少合适，这题之前写过被坑了好几次，其次π的值要求也比较高
#include<iostream>
using namespace std;
typedef long long int ll;
ll myf(ll n) {
ll ans = 0;
while (n) {
ans += n / 5;
n /= 5;
}
return ans;
}
int main()
{
int num;
cin >> num;
int i = 1;
while (i<=num)
{
ll q;
cin >> q;
ll rights = 2000000000, lefts = 0, mid;
while (lefts <= rights)
{
mid = (rights + lefts) / 2;
if (myf(mid) < q)lefts = mid + 1;
else rights = mid - 1;
}
if (q == myf(lefts)) {
printf("Case %d: %lld\n", i, lefts);
}
else printf("Case %d: impossible\n", i);
i++;
}
}
问题I
思路：这道题感觉比前两题好点，既不用考虑精度，也不难转化.所以我没编check函数，，
#include<cstdio>
#include<iostream>
using namespace std;
double myf(double x)
{
return (8 * x * x * x * x + 7 * x * x * x + 2 * x * x + 3 * x + 6);
}
int main()
{
int num;
cin >> num;
while (num--)
{
double x;
scanf("%lf", &x);
if (myf(0) > x || myf(100) < x)
{
printf("No solution!\n");
continue;
}
double lefts = 0, rights = 100.0;
double mid = 50.0;
while (fabs(myf(mid) - x) > 1e-5)
{
if ((myf(mid) > x)) rights = mid;
else if (myf(mid) < x) lefts = mid;
mid = (lefts + rights)/2;
}
printf("%.4lf\n", mid);
}
return 0;
}</iostream></cstdio></iostream></iostream></iostream></iostream></cstdio></iostream></iostream></iostream></iostream>