A - A^B Mod C

Give three positive integers a, B, C and find A^B Mod C.

For example, 3 5 8, 3^5 Mod 8 = 3.

Input

Three positive integers a, B, C, separated by spaces. (1 <= A,B,C <= 10^9)

Output

Output calculation results

Sample Input

3 5 8

Sample Output

3

#include<stdio.h>
#include<math.h>

int main ()
{ 
unsigned long long int A, C;	
	unsigned long long int ans=1,B;
	scanf("%llu %llu %llu",&A,&B,&C);
	A=A%C;
	while(B>0){
		if(B%2==1)
			ans=(ans*A)%C;
		B=B/2;
		A=(A*A)%C;
		
	}
	printf("%llu", ans);
}

C - number of decision primes

Enter two integers x and Y, and output the number of primes (including X and Y) between - > >.

Input

Two integers X and Y (1 < = X, y < = 105).

Output

Output an integer representing the number of primes between X and Y (including X and y).

Sample Input

1 100

Sample Output

25

#include<stdio.h>
#include<math.h>

int prime(int p) {
	if (p <= 1)
		return 0;
	for (int i = 2; i <= (sqrt(p)); i++)
		
	{
		if (p % i == 0) {
			return 0;
		}
	}
	return 1;
}

int main()

{
	int count = 0;
	int X, Y;
	scanf("%d %d", &X, &Y);
	if (X < Y) {
		for (int i = X; i <= Y; i++) {
		if(	prime(i))
			count++;
			
		}
	} else {
		for (int i = Y; i<= X; i++) {
			if(prime(i))
			count++;
			
		}
	}
	printf("%d", count);
	return 0;
}

D - matrix multiplication

Calculate the multiplication of two matrices. n \times mn × Matrix of order m ＾ AA ＾ multiplied by ＾ m \times km × The matrix ＾ CC ＾ obtained by k ＾ order matrix ＾ BB ＾ is ＾ n \times kn × k order, and C[i][j] = A[i][0] \times B[0][j] + A[i][1] \times B[1][j] +... + A[i][m-1] \times B[m-1][j](C[i][j]C[i][j]=A[i][0] × B[0][j]+A[i][1] × B[1][j]+……+A[i][m−1] × B[m − 1][j](C[i][j] represents the element in the − ii − row and − jj − column of the − CC − matrix).

Input format

The first line, n, m, kn,m,k, indicates that the AA matrix is the nn row and the BB matrix is the mm row and the kk column, and n, m, kn,m,k are all less than 100;

Then input two matrices, AA # and BB # successively, AA # matrix # nn # row # mm # column, BB # matrix # mm # row # kk # column. The absolute value of each element in the matrix will not be greater than # 1000.

Output format

The output matrix is ＾ CC, a total of ＾ nn ＾ rows, with ＾ kk ＾ integers in each row, separated by a space.

Sample Input

3 2 3
1 1
1 1
1 1
1 1 1
1 1 1

Sample Output

2 2 2
2 2 2
2 2 2

#include<stdio.h>
int main(){
	int A[100][100],B[100][100],C[100][100]={0};
	int n,m,k,i,j,t;
	scanf("%d%d%d",&n,&m,&k);
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			scanf("%d",&A[i][j]);
		}
	}
	for(i=0;i<m;i++){
		for(j=0;j<k;j++){
			scanf("%d",&B[i][j]);
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<k;j++){
			for(t=0;t<m;t++){
				C[i][j]=C[i][j]+A[i][t]*B[t][j];
			}
			printf("%d ",C[i][j]);
		}
		printf("\n");	
	}
	return 0;
} 

E - Bash game

There is a pile of stones, a total of N. A and B take turns. A takes it first. Take at least one stone at a time and K at most. The one who gets the last stone wins. Suppose a and B are very smart, and there will be no mistakes in the process of taking stones. Give N and K and ask who can win the game in the end.

For example, N = 3, K = 2. No matter how A takes it, B can get the last stone.

Input

Line 1: a number T, which represents the number of numbers used as input tests later. (1 < = T < = 10000) line 2 - T + 1: 2 numbers n, K per line. The middle is separated by a space. (1 <= N,K <= 10^9)

Output

A total of T lines, if a wins, output a, if B wins, output B.

Sample Input

4
3 2
4 2
7 3
8 3

Sample Output

B
A
A
B

#include<stdio.h>
int main()
{
   int N,K;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&N,&K);
        if(N%(K+1))
        printf("A\n");
        else
        printf("B\n");
    }
}

F - stone game

There are two piles of stones in any number, which can be different. At the beginning of the game, two people take turns to take stones. The game stipulates that there are two different methods to take each time. One is to take any number of stones from any pile; Second, the same number of stones can be taken from the two piles at the same time. Finally, the winner is the one who takes all the stones. Now give the initial number of two piles of stones. If it's your turn to take first, suppose both sides adopt the best strategy, and ask whether you are the winner or the loser in the end.

Input

The input contains several lines, indicating the initial conditions of several kinds of stones. Each line contains two non negative integers a and b, indicating the number of two piles of stones. A and b are not greater than 1000000000.

Output

There are also several lines corresponding to the output. Each line contains a number 1 or 0. If you are the winner in the end, it is 1, otherwise, it is 0.

Sample Input

2 1
8 4
4 7

Sample Output

0
1
0

#include <stdio.h>
#include <math.h>
#include <string.h>
const double Gsr=(1+sqrt(5.0))/2;
void swap(int *a,int *b)
{
	int t=*b;
	*b=*a;
	*a=t;
}
int main()
{
	int a,b;
	while(~scanf("%d%d",&a,&b))
	{
		if(a>b)
		{
			swap(&a,&b);
		}
		if(a == (int)(Gsr*(b-a))) //Strange situation, lose first
			puts("0");
		else
			puts("1");
	}
	return 0;
}

G - Matches Game

This is a simple game. In this game, there are several piles of matches and two players. The two players take turns. In each round, players can select a pile and take out any number of matches from the pile (of course, the number of matches taken out cannot be zero or greater than the number of matches in the selected pile). If a player takes matches and there are no matches left, the player is the winner. It is assumed that both players will make the best decision. Your job is to judge whether the first player can win the game.

Input

The input consists of several lines, each with a test case. At the beginning of a line, there is an integer M (1 < = M < = 20), which is the number of matchstacks. Then M positive integers no greater than 10000000. These M integers represent the number of matches in each stack.

Output

For each test case, if the first player wins, output "Yes" in one line, otherwise output "No".

Sample Input

2 45 45
3 3 6 9

Sample Output

No
Yes

#include <bits/stdc++.h>
using namespace std;
int main(){
	int m,n;
	while(scanf("%d",&m)!=EOF){
		int mid;
		for(int i=0;i<m;i++){
			cin>>n;
			if(i==0){
				mid=n;
				continue;
			}

			mid^=n;
		}
		if(!mid){
			cout<<"No"<<endl;
		}else cout<<"Yes"<<endl;
	}
	return 0;
}

H - number of Coprime numbers (I)

Here we define \ varphi(n) φ (n) Represents the number of all coprime numbers less than or equal to {nn} and {nn}.

For example \ varphi(10) = 4 φ (10) = 4, because we can find the coprime of 1,3,7,91,3,7,9 and 1010 in 1 \sim 101 ∼ 10.

Input format

In the first line, enter an integer, {tt, indicating the number of test data groups.

Next, there are ， tt ， lines, and each line has an integer ， nn.

Output format

For each set of test data output \ varphi(n) φ (n) .

Data range

1 \le t \le 100, 1 \le n \le 10^{10}1≤t≤100,1≤n≤1010.

Sample Input

3
2
10
100

Sample Output

1
4
40

#include<stdio.h>
#include<math.h>

int huzhi(int a, int b) {
	int  t;
	if (a < b) {
		t = a;
		a = b;
		b = t;
		
	}
	while (a % b) {
		t = b;
		b = a % b;
		a = t;
	}
	return b;
}

int main() {
	int t, n;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		 int count = 0;
		scanf("%d", &n);
		for (int j =1; j<=n; j++) {
			if ( huzhi(n, j)==1)
				count++;
		}
		printf("%d", count);
	}
	return 0;
}

Timeout?

#include<stdio.h>
#include<math.h>

long long int fun(long long int n) {
	long long int t = n, i, m;
	for (i = 2; i * i < n; i++) {
		
		if (n % i == 0) {
			t = (t / i) * (i - 1);
			while (n % i == 0) {
				n /= i;
			}
		}
	}
	if (n > 1) t = t / n * (n - 1);
	return t;
}

int main() {
	long long int N, i, n, count;
	scanf("lld", &N);
	for (i = 0; i < N; i++) {
		scanf("%lld", &n);
		count = fun(n);
		printf("%lld\n", count);
	}
	return 0;
}

Solving timeout problem with Euler function