HPU Summer Training Day x（河南理工大学暑期第x天）

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<stdio.h>
#include<math.h>
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 <iostream>
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<cstdio>
#include<cmath>
#include<algorithm>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
typedef long long ll;
ll p[maxn];
ll a[maxn];
bool check(ll x)
{
    if(p[x])    return 0;
    ll mid=0;
    while(x)
    {
        mid+=x%10;x/=10;
    }
    if(p[mid])    return 0;
    else    return 1;
}
int main()
{
    p[0]=p[1]=1;
    for(ll i=2;i<sqrt(maxn);i++)
    {
        for(ll j=i*2;j<maxn;j+=i)
        {
            p[j]=1;
        }
    }
    a[0]=0;
    for(int i=1;i<maxn;i++)
    {
        if(check(i))    a[i]=a[i-1]+1;
        else    a[i]=a[i-1];
    }
    ll t,l,r;
    while(~scanf("%lld",&t))
    {
        for(int i=1;i<=t;i++)
        {
            scanf("%lld %lld",&l,&r);
            printf("Case #%lld: %lld\n",i,a[r]-a[l-1]);
        }
    }
    return 0;
}

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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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;
    }
}