密码HPUACM
A - Pseudoprime numbers
Fermat's theorem states that for any prime number p and for any integer a > 1, ap = a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)
Given 2 < p ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.
Input
Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.Output
For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".Sample Input
3 2
10 3
341 2
341 3
1105 2
1105 3
0 0
Sample Output
no
no
yes
no
yes
yes
本题关键点有二，一是素数的判断，二是a^p的计算，使用快速幂可降低运算次数；需注意int的长度，所以使用__int64。
#include<cstdio>
#include<iostream>
int MID(__int64 a,__int64 b,__int64 mod){
__int64 ans=1,x=a;
while(b){
if(b&1){
ans=(x*ans)%mod;
}
x=(x*x)%mod;
b>>=1;
}
return ans;
}
int main(){
__int64 p,a;
__int64 mod;
while(scanf("%I64d%I64d",&p,&a)&&p||a){
int num=0;
for(int i=2;i*i<p;i++){
if(p%i==0)
num++;
}
if(num==0)
printf("no\n");
else{
mod=p;
if(MID(a,p,mod)==a)
printf("yes\n");
else
printf("no\n");
}
}
return 0;
}B - Raising Modulo Numbers
People are different. Some secretly read magazines full of interesting girls' pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODáKH. The rules follow:
Each player chooses two numbers Ai and Bi and writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressions AiBi from all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players' experience it is possible to increase the difficulty by choosing higher numbers.
You should write a program that calculates the result and is able to find out who won the game.
Input
The input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Then the assignements follow. Each assignement begins with line containing an integer M (1 <= M <= 45000). The sum will be divided by this number. Next line contains number of players H (1 <= H <= 45000). Next exactly H lines follow. On each line, there are exactly two numbers Ai and Bi separated by space. Both numbers cannot be equal zero at the same time.
Output
For each assingnement there is the only one line of output. On this line, there is a number, the result of expression
(A1B1+A2B2+ ... +AHBH)mod M.Sample Input
3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132
Sample Output
2
13195
13
本题考查的同A题一样为快速幂，题意为（A1^B1+A2^B2+。。。+AH^BH）%M.考虑到长度问题，每次计算都要取余，因此有
if (b & 1)
ans = ans * a % mod;
a = a * a % mod;且依然使用__int64型。
#include<iostream>
using namespace std;
__int64 a[50000], b[50000];
__int64 mid(__int64 a, __int64 b, __int64 mod) {
__int64 ans = 1;
while (b) {
if (b & 1)ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int main() {
__int64 z, m, h, num;
cin >> z;
for (__int64 i = 0; i < z; i++) {
cin >> m >> h;
num = 0;
for (__int64 j = 0; j < h; j++) {
cin >> a[j] >> b[j];
}
for (__int64 j = 0; j < h; j++) {
num += mid(a[j], b[j], m);
}
cout << num % m << '\n';
}
return 0;
}C - Key Set
soda has a set S with n integers {1,2,…,n}. A set is called key set if the sum of integers in the set is an even number. He wants to know how many nonempty subsets of S are key set.
Input
There are multiple test cases. The first line of input contains an integer T (1≤T≤10^5), indicating the number of test cases. For each test case:The first line contains an integer n (1≤n≤10^9), the number of integers in the set.
Output
For each test case, output the number of key sets modulo 1000000007.
Sample Input
4
1
2
3
4
Sample Output
0
1
3
7
本题依然是考察快速幂，题意大致为一个由1到n的集合的非空子集有多少个集合的元素和为偶数。通过判断可知应为2^(n-1)-1个，利用快速幂解题。
#include<iostream>
typedef __int64 l;
using namespace std;
l mid(l a, l b, l m) {
l ans = 1;
while (b) {
if (b & 1) ans = ans * a % m;
a = a * a % m;
b = b / 2;
}
return ans;
}
int main() {
l n, num;
int m;
l mod = 1000000007;
cin >> m;
for (int i = 0; i < m; i++){
cin >> n;
num = mid(2, n - 1, mod) - 1;
cout << num << endl;
}
return 0;
}D - Distribution money
AFA want to distribution her money to somebody.She divide her money into n same parts.One who want to get the money can get more than one part.But if one man's money is more than the sum of all others'.He shoule be punished.Each one who get a part of money would write down his ID on that part.
Input
There are multiply cases.
For each case,there is a single integer n(1<=n<=1000) in first line.
In second line,there are n integer a1,a2...an(0<=ai<10000)ai is the the ith man's ID.
Output
Output ID of the man who should be punished.
If nobody should be punished,output -1.
Sample Input
3
1 1 2
4
2 1 4 3
Sample Output
1
-1
本题题意为计算是否有元素个数超过了总数的一半，直接利用数组来计算，暴力求解就好。
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n;
while (scanf("%d", &n) != EOF) {
int p = 0, k[10005] = { 0 };
int a[10005];
for (int i = 0; i < n; i++){
cin >> a[i];
k[a[i]]++;
if (k[a[i]] > n - k[a[i]]) {
p = a[i];
}
}
if (p != 0)
cout << p << '\n';
else
cout << "-1\n";
}
return 0;
}E - Rightmost Digit
Given a positive integer N, you should output the most right digit of N^N.
Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).
Output
For each test case, you should output the rightmost digit of N^N.
Sample Input
2
3
4
Sample Output
7
6
Hint
In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7.
In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.
本题要求求出n^n的最右数字，即末尾数，依然使用快速幂求解即可
#include<iostream>
typedef long long ll;
using namespace std;
ll mid(ll a) {
ll ans = 1;
ll b = a;
while (b) {
if (b & 1) ans = ans * a % 10;
a = a * a % 10;
b /= 2;
}
return ans;
}
int main() {
ll t, n;
cin >> t;
for (int i = 0; i < t; i++){
cin >> n;
cout << mid(n) << '\n';
}
return 0;
}F - 人见人爱A^B
求A^B的最后三位数表示的整数。
说明：A^B的含义是“A的B次方”
Input
输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。
Output
对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。
Sample Input
2 3
12 6
6789 10000
0 0
Sample Output
8
984
1
A^B，考察快速幂
#include<iostream>
using namespace std;
long long int pown(long long int x, long long int b) {
long long int ans=1;
while (b) {
if (b & 1) ans = (ans * x) % 1000;
x = (x * x) % 1000;
b = b / 2;
}
return ans;
}
int main() {
long long int a, b;
long long int num;
while (1) {
cin >> a >> b;
if (a == 0 && b == 0)
break;
num = pown(a, b);
num %= 1000;
cout << num << endl;
}
}G - Trailing Zeroes (III)
You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 12...*N. For example, 5! = 120, 120 contains one zero on the trail.
Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.Each case contains an integer Q (1 ≤ Q ≤ 108) in a line.
Output
For each case, print the case number and N. If no solution is found then print 'impossible'.Sample Input
3
1
2
5Sample Output
Case 1: 5
Case 2: 10
Case 3: impossible
本题题意在于判断阶乘是否有满足末尾有N个0的情况并输出满足最小的数字，若不满足输出impossible。使用二分法，并编写TW函数使其能判断包含5的个数：
int TW(int n) {
int ans = 0;
while (n) {
ans += n / 5;
n = n / 5;
}return ans;
}之后输出结果
#include<iostream>
typedef long long ll;
using namespace std;
int TW(int n) {
int ans = 0;
while (n) {
ans += n / 5;
n = n / 5;
}return ans;
}
int serch(int n) {
int less = 0, max = 5 * n +100, mid;
while (less <= max) {
mid = (less + max) / 2;
if (TW(mid) < n)
less = mid + 1;
else
max = mid - 1;
}
if (TW(less) == n)
return less;
else
return 0;
}
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++){
int q, num=0, n=5, k=4;
cin >> q;
cout << "Case " << i + 1 << ": ";
if (serch(q) == 0)
printf("impossible\n");
else
printf("%d\n", serch(q));
}
return 0;
}H - Pie
My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though.
My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size.
What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.
Input
One line with a positive integer: the number of test cases. Then for each test case:
---One line with two integers N and F with 1 <= N, F <= 10 000: the number of pies and the number of friends.
---One line with N integers ri with 1 <= ri <= 10 000: the radii of the pies.
Output
For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10^(-3).
Sample Input
3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2
Sample Output
25.1327
3.1416
50.2655
本题题意为 分馅饼，馅饼不能组合，只能把一整块去除掉，因此使用二分法，并对数组排序后编写函数判断分得的馅饼大小是否满足人数而且最大：
double check(double ans) {
int mid = 0;
for (int i = 0; i < n; i++) {
mid += (int)(r[i] / ans);
}
return mid;
}返回值便是可以满足的人数，再通过
if (check(ans) >= p + 1)
判断。因有精度要求为1e-3，而面积最大为Π（1000010000），通过计算得出要满足1e-3的精度，100000000/2^44就可满足，因此循环44次便可满足其精度，之后输出便可
#include <iostream>
#include <cstdio>
#include <algorithm>
#define PAI acos(-1.0)
using namespace std;
int t, n, p;
double r[10005], v;
double check(double ans) {
int mid = 0;
for (int i = 0; i < n; i++) {
mid += (int)(r[i] / ans);
}
return mid;
}
double Dic(double n) {
double less = 0, max = n, ans, mid;
int num = 44;
while (num--) {
ans = (less + max) / 2;
if (check(ans) >= p + 1) {
mid = ans;
less = ans;
}
else
max = ans;
}
return mid;
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &p);
for (int i = 0; i < n; i++) {
scanf("%lf", &v);
r[i] = v * v * PAI;
}
sort(r, r + n);
printf("%.4lf\n", Dic(r[n - 1] + 10.0));
}
return 0;
}
京公网安备 11010502036488号