HPU 暑期集训 Day X
主要学的是快速幂，gcd
I don't know what day this is,just record it.
Pseudoprime numbers
Description:
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
Problem solving:
First judge p is a prime number or not,if p is a prime number output 'no',else then judge a^p%p is equal to a or not,if not equal output 'no'.We should use fast power to avoid TLE.
Code:
#include
#include
int s(long long a)
{
if(a==2)
return 1;
for(int i=2;i*i<=a;i++)
if(a%i==0)
return 0;
return 1;
}
long long f(long long a,long long b,long long c)//快速幂模板
{
long long t=1;
a=a%c;
while(b>0)
{
if(b%2==1)
t=t*a%c;
b=b/2;
a=a*a%c;
}
return t;
}
int main()
{
long long a,p;
while(~scanf("%lld%lld",&p,&a)&&!(a==0&&p==0))
{
if(s(p))
printf("no\n");
else
{
if(f(a,p,p)==a)
printf("yes\n");
else
printf("no\n");
}
}
return 0;
}Raising Modulo Numbers
Description:
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 Ai Bi 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
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
Problem solving:
I don't understand this problem clearly first time,and then I find a little hint in the output,so it's easy now.
Code:
#include
using namespace std;
typedef long long ll;
ll poww(ll x, ll y, ll maxn)
{
ll res = 1;
while (y)
{
if (y % 2 != 0)
res = res * x % maxn;
x = x * x % maxn;
y /= 2;
}
return res % maxn;
}
int main()
{
ll n;
cin >> n;
ll a, b, c, d, e;
while (n--)
{
ll sum = 0;
cin >> a >> b;
while (b--)
{
cin >> d >> e;
sum += poww(d, e, a);
sum %= a;
}
cout << sum << endl;
}
}
Wolf and Rabbit
Description:
There is a hill with n holes around. The holes are signed from 0 to n-1.
A rabbit must hide in one of the holes. A wolf searches the rabbit in anticlockwise order. The first hole he get into is the one signed with 0. Then he will get into the hole every m holes. For example, m=2 and n=6, the wolf will get into the holes which are signed 0,2,4,0. If the rabbit hides in the hole which signed 1,3 or 5, she will survive. So we call these holes the safe holes.
Input
The input starts with a positive integer P which indicates the number of test cases. Then on the following P lines,each line consists 2 positive integer m and n(0<m,n<2147483648).
Output
For each input m n, if safe holes exist, you should output "YES", else output "NO" in a single line.
Sample Input
2
1 2
2 2
Sample Output
NO
YES
Problem solving:
Nothing to say,just judge the gcd of m and n is equal to 1 or not.
Code:
#include
#include
#include
using namespace std;
int main()
{
int n,a,b;
scanf("%d",&n);
while(n--)
{
scanf("%d %d",&a,&b);
if(__gcd(a,b)==1) puts("NO");
else puts("YES");
}
}Cake
Description:
一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要将蛋糕切成多少块(每块大小不一定相等),才能使p人或者q人出席的任何一种情况,都能平均将蛋糕分食.
Input
每行有两个数p和q.
Output
输出最少要将蛋糕切成多少块.
Sample Input
2 3
Sample Output
4
Hint
将蛋糕切成大小分别为1/3,1/3,1/6,1/6的四块即满足要求.
当2个人来时，每人可以吃1/3+1/6=1/2 , 1/2块。
当3个人来时，每人可以吃1/6+1/6=1/3 , 1/3, 1/3块。
Code:
#include
using namespace std;
int main()
{
int p, q;
while (~scanf("%d %d", &p, &q))
{
cout << p + q - __gcd(p, q) << endl;
}
}又见GCD
Description:
有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a和c的最大公约数为b，现已知a和b，求满足条件的最小的c。
Input
第一行输入一个n，表示有n组测试数据，接下来的n行，每行输入两个正整数a,b。
Output
输出对应的c，每组测试数据占一行。
Sample Input
2
6 2
12 4
Sample Output
4
8
Problem solving:
What we would like to find is the smallest c,so begin with 2*b.
Code:
#include
using namespace std;
int main()
{
int n, a, b;
cin >> n;
while (n--)
{
cin >> a >> b;
for (int i = b * 2; ; i += b)
{
if (__gcd(a, i) == b)
{
cout << i << endl; break;
}
}
}
}最小公倍数
Description:
给定两个正整数，计算这两个数的最小公倍数。
Input
输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数.
Output
对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。
Sample Input
10 14
Sample Output
70
Code:
#include
using namespace std;
typedef long long ll;
int main()
{
ll n, a, b;
while (~scanf("%lld %lld", &a, &b))
{
cout << a * b / __gcd(a, b) << endl;
}
}素数判定
Description:
对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x<y<=50)，判定该表达式的值是否都为素数。
Input
输入数据有多组，每组占一行，由两个整数x，y组成，当x=0,y=0时，表示输入结束，该行不做处理。
Output
对于每个给定范围内的取值，如果表达式的值都为素数，则输出"OK",否则请输出“Sorry”,每组输出占一行。
Sample Input
0 1
0 0
Sample Output
OK
Code:
#include
using namespace std;
typedef long long ll;
bool check(ll x)
{
if (x == 2)
return 0;
for (int i = 2; i < sqrt(x + 1); i++)
{
if (x % i == 0)
return 1;
}
return 0;
}
int main()
{
ll n, a, b;
while (scanf("%lld %lld", &a, &b))
{
int flag = 0;
if (a == 0 && b == 0)
break;
for (ll i = a; i <= b; i++)
{
ll mid = i*i+ i + 41;
if (check(mid))
{
flag = 1;
break;
}
}
if (flag)
puts("Sorry");
else
puts("OK");
}
}分拆素数和
Description:
把一个偶数拆成两个不同素数的和，有几种拆法呢？
Input
输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。
Output
对应每个偶数，输出其拆成不同素数的个数，每个结果占一行。
Sample Input
30
26
0
Sample Output
3
2
Code:
#include
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 7;
int p[maxn];
int main()
{
for (int i = 0; i < maxn; i++)
p[i] = 1;
p[0] = p[1] = 0;
for (int i = 2; i <= sqrt(maxn + 1); i++)
{
for (int j = i + i; j < maxn; j += i)
{
p[j] = 0;
}
}
ll n, a, b;
while (scanf("%lld", &n))
{
if (n == 0)
break;
int ans = 0;
for (int i = 2; i <n / 2; i++)
{
if (p[i] && p[n - i])
ans++;
}
cout << ans << endl;
}
}美素数
Description:
小明对数的研究比较热爱，一谈到数，脑子里就涌现出好多数的问题，今天，小明想考考你对素数的认识。
问题是这样的：一个十进制数，如果是素数，而且它的各位数字和也是素数，则称之为“美素数”，如29，本身是素数，而且2+9 = 11也是素数，所以它是美素数。
给定一个区间，你能计算出这个区间内有多少个美素数吗？
Input
第一行输入一个正整数T，表示总共有T组数据(T <= 10000)。
接下来共T行，每行输入两个整数L，R(1<= L <= R <= 1000000)，表示区间的左值和右值。
Output
对于每组数据，先输出Case数，然后输出区间内美素数的个数（包括端点值L,R）。
每组数据占一行，具体输出格式参见样例。
Sample Input
3
1 100
2 2
3 19
Sample Output
Case #1: 14
Case #2: 1
Case #3: 4
Problem solving:
Just By meter(打表).
Code:
#include
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 7;
int p[maxn];
int main()
{
for (int i = 0; i < maxn; i++)
p[i] = 1;
p[0] = p[1] = 0;
for (int i = 2; i <= sqrt(maxn + 1); i++)
{
for (int j = i + i; j < maxn; j += i)
{
p[j] = 0;
}
}
ll n, a, b;
while (scanf("%lld", &n))
{
if (n == 0)
break;
int ans = 0;
for (int i = 2; i <n / 2; i++)
{
if (p[i] && p[n - i])
ans++;
}
cout << ans << endl;
}
}Key Set
Description:
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≤1e5), indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤1e9), 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
Problem solving:
The answer is 2^(a-1)-1
Code:
#include
using namespace std;
typedef long long ll;
const int maxn = 1000000007;
ll poww(ll x, ll y)
{
ll res = 1;
while (y)
{
if (y % 2 != 0)
res = res * x % maxn;
x = x * x % maxn;
y /= 2;
}
return res % maxn;
}
int main()
{
int n, a, b;
cin >> n;
while (n--)
{
cin >> a;
cout << poww(2, a - 1) - 1 << endl;
}
}人见人爱A^B
Description:
求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
Problem solving:
Fast power.
Code:
#include
using namespace std;
typedef long long ll;
ll poww(ll x, ll y, ll z)
{
ll ans = 1, base = x; while (y != 0)
{
if (y & 1 != 0)
ans = ans * base % z;
base = (base % z) * (base % z) % z; y >>= 1;
}
return ans;
}
int main()
{
ll a, b;
while (scanf("%lld %lld", &a, &b))
{
if (a == 0 && b == 0)
break;
cout << poww(a, b, 1000) << endl;
}
}Rightmost Digit
Description:
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.
Problem solving:
Fast power.
Code:
#include
using namespace std;
typedef long long ll;
ll poww(ll x, ll y, ll z)
{
ll ans = 1, base = x; while (y != 0)
{
if (y & 1 != 0)
ans = ans * base % z;
base = (base % z) * (base % z) % z; y >>= 1;
}
return ans;
}
int main()
{
ll n, a;
cin >> n;
while (n--)
{
cin >> a;
cout << poww(a, a, 10) << endl;
}
}
查看9道真题和解析
