### 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:

Input

Output

Sample Input

2 3

Sample Output

4

Hint

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:

Input

Output

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

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:

Input

Output

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

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

Output

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:
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:

Input

Output

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;
}
}