原理

int p(int a,int b){
int t,y;  //定义两个变量，t起到类乘的作用，而y则就是每一次要乘的数
t=1; y=a;  //注意一定要初始化
while (b!=0){  //只要二进制位数还没有遍历完就还要循环
if (b&1==1) t=t*y; //y就是幂的形式a^(2^0),a^(2^1),a^(2^2),a^(2^3)
y=y*y;  //
b=b>>1;  //每次要舍去二进制数的最后一位
}
return t;
}


题目

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


AC代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long p(long long a,long long b){
long long t,y,n=b;
t=1; y=a;
while (b!=0){
if (b&1==1) t=t*y%n;
y=y*y%n;
b=b>>1;
}
return t;
}
int main()
{
long long m,n;
while(scanf("%lld %lld",&m,&n)!=EOF){
if(m==0&&n==0) break;
int flag=0;
for(int i=2;i*i<=m;i++){
if(m%i==0){
flag=1;
break;
}
}
if(flag==0) cout<<"no"<<endl;
else{
if(p(n,m)==n) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
}
}


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.


AC代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long p(long long a){
long long t,y;
t=1; y=a;
while(a!=0){
if (a&1==1) t=t*y%10;
y=y*y%10;
a=a>>1;
}
return t;
}
int main()
{
int t;
cin>>t;
while(t--){
long long n;
scanf("%lld",&n);
cout<<p(n)<<endl;
}
}


3 2000


Tuesday


AC代码

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
using namespace std;
typedef long long ll;
ll p(ll a,ll b){
int t,y;
t=1; y=a;
while (b!=0){
if (b&1==1) t=t*y%7;
y=y*y%7;
b=b>>1;
}
return t;
}
int main()
{
int a,b;
cin>>a>>b;
switch(p(a,b)){
case 1: printf("Monday\n");break;
case 2: printf("Tuesday\n");break;
case 3: printf("Wednesday\n");break;
case 4: printf("Thursday\n");break;
case 5: printf("Friday\n");break;
case 6: printf("Saturday \n");break;
case 0: printf("Sunday\n");break;
}
}