A. Arpa’s hard exam and Mehrdad’s naive cheat
There exists an island called Arpa’s land, some beautiful girls live there, as ugly ones do.
Mehrdad wants to become minister of Arpa’s land. Arpa has prepared an exam. Exam has only one question, given n, print the last digit of 1378n.
Mehrdad has become quite confused and wants you to help him. Please help, although it’s a naive cheat.
Input
The single line of input contains one integer n (0 ≤ n ≤ 109).
Output
Print single integer — the last digit of 1378n.
Examples
input
1
output
8
input
2
output
4
Note
In the first example, last digit of 13781 = 1378 is 8.
In the second example, last digit of 13782 = 1378·1378 = 1898884 is 4.
规律题简单；一直算最后一位8相乘就可以知道
规律是：8 4 2 6循环
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;
const int MM=10;
int main()
{
int t;
scanf("%d",&t);
ll sum=1;
if(t==0)
cout<<"1"<<endl;
else {
if(t%4==1)
cout<<"8"<<endl;
else if(t%4==2)
cout<<"4"<<endl;
else if(t%4==3)
cout<<"2"<<endl;
else if(t%4==0)
{
printf("6\n");
}
}
return 0;
}
B. Arpa’s obvious problem and Mehrdad’s terrible solution
There are some beautiful girls in Arpa’s land as mentioned before.
Once Arpa came up with an obvious problem:
Given an array and a number x, count the number of pairs of indices i, j (1 ≤ i < j ≤ n) such that , where is bitwise xor operation (see notes for explanation).
Immediately, Mehrdad discovered a terrible solution that nobody trusted. Now Arpa needs your help to implement the solution to that problem.
Input
First line contains two integers n and x (1 ≤ n ≤ 105, 0 ≤ x ≤ 105) — the number of elements in the array and the integer x.
Second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 105) — the elements of the array.
Output
Print a single integer: the answer to the problem.
Examples
input
2 3
1 2
output
1
input
6 1
5 1 2 3 4 1
output
2
Note
In the first sample there is only one pair of i = 1 and j = 2. so the answer is 1.
In the second sample the only two pairs are i = 3, j = 4 (since ) and i = 1, j = 5 (since ).
A bitwise xor takes two bit integers of equal length and performs the logical xor operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. You can read more about bitwise xor operation here: https://en.wikipedia.org/wiki/Bitwise_operation#XOR.
题意 简单 ：
异或
1.a^b = c，则：a = b^c，b = a^c。说明：a如果与某个数的异或为c， 那么这个数是唯一的，且可直接求出：b = a^c。
2.c用于记录某个数出现的次数，一边读取数一边操作：假设当前读取的数据为a，则与之对应的数为x^a，
则表明a能够与c[xa]个xa组成一对，所以 ans += c[x^a]，然后再更新a出现的次数，即c[a]++。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;
const int MM=1e5+5;
int a[MM<<1];
int main()
{
int n,x;
scanf("%d %d",&n,&x);
ll sum,ans=0;
for(int i=0; i<n; i++)
{
scanf("%d",&sum);
ans+=a[x^sum];
a[sum]++;
}
cout<<ans;
return 0;
}
京公网安备 11010502036488号