题目链接
Astronomers have recently found a cosmic signal from a distant planet. World’s best scientists have all confirmed that this is a communication signal sent by aliens. Moreover, they have established that these aliens have only nine fingers, hence, they use a numeral system in base 9, in other words, digits from 0 to 8. To challenge humans, these aliens came up with a puzzle. Many scientists solved the puzzle, but since the stakes are very high, they want you to confirm that their solution is correct as you are the smartest computer scientist on the planet. The puzzle is explained below.
Let n be some positive integer, and f(n) be a function that returns another positive integer that can be represented as 123456781011…n in base 9. In other words, f(n) is a number which can be obtained by concatenating all the positive integers from 1 to n in their base 9 representations. The obtained number is also in base 9.
For example, for n=10 (in base 10), f(n)=123456781011, since n=11 (in base 9). You need to find the remainder of dividing f(n) by 4.
Input
Input consists of a single integer n (1≤n≤1018) given in base 10.
Output
Print a single integer equal to f(n) modulo 4.
Example
inputCopy
5
outputCopy
3
题意：首先给出一个n，f(n)表示1234567810…n,共有n个数，9进制，求其十进制mod4的值。
题解：数据量很大，所以肯定不是暴力，我们得找规律，例如：我们以12345678 为例：
12345678 = 8+7 * 9+6 * 9 ^ 2+……+19 ^ 7
根据模的加法得：
(a+b+c)%n=(a%n+b%n+c%n)%n;
根据模的乘法得：
(ab)%n=(a%n*b%n)%n;
以上的式子可以写为(8%4+7%4 * 9%4%4+……+1%4 * 9 ^ 7 %4 % 4) %4
通过简单的证明可得：
9 ^ n % 4 = (9 % 4 * 9 % 4……)% 4 =(1 * 1 * 1 ……) %4=1
所以式子可以写成：
(8%4+7%4+6%4+……+1%4)%4;
然后我们简答的打一个表
1 2 3 4 5 6 7 8
10 11 12 13 14 15 16 17 18
20 21 22 23 24 25 26 27 28
30 31 32 33 34 35 36 37 38
40 41 42 43 44 45 46 47 48
50 51 52 53 54 55 56 57 58
60 61 62 63 64 65 66 67 68
………………………………
我们可以发现除了第一组外
其余都是九个一组，而每一组中除第一个数外其余除最后一个数外，其他都相同 我们可以认为是某一个数mod4后乘8，原式相当于(x+8 * n) %4 删去后不会对结果产生影响，所以我们不用去管他，所以我们现在的题目简化成只需要找那些结尾是0的数的个数，我们在这给他们单列一下
%4
10 1
20 2
30 3
40 0
50 1
60 2
70 3
80 0
100 1
循环往复所以我们可以找到他们的组数分别加上相应的1，2，3即可.具体见以下AC代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
signed main()
{
int n;cin>>n;int sum=0;if(n<=8){
for(int i=1; i<=n; i++){
sum+=i%4;}printf("%lld\n",sum%4);return 0;}int x=n%9;//最后一个数的末位数字int k=n;while(k){
int bit=k%9;k/=9;sum+=bit%4;}k=sum-x%4;//最后一个数前面(x-1)个数的与x相同部分的值sum+=k*(x-1);for(int i=1;i<=x-1;i++){
sum+=(i%4);}n-=(x+1);//成串的有几个数int num=(n-8)/9;//成九个的有几对num+=1;//总共有几个代0的int ans=num/4;sum+=ans*1+ans*2+ans*3;for(int i=1;i<=num%4;i++){
sum+=(i%4);}printf("%lld\n",sum%4);return 0;
}
注：我们在这个题中千万要注意的一点是要完全按照mod的加法运算的规则，要在正确的位置进行求mod
下面是WA5的代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
signed main()
{
int n;cin>>n;int sum=0;if(n<=8){
for(int i=1; i<=n; i++){
sum+=i;}printf("%lld\n",sum%4);return 0;}int x=n%9;//最后一个数的末位数字int k=n;while(k){
int bit=k%9;k/=9;sum+=bit;}sum*=x;for(int i=1; i<=x; ++i){
sum-=(x-i);}n-=(x+1);int num=(n-8)/9;num+=1;printf("%lld\n",(num%4+sum%4)%4);return 0;
}
这个代码因为没有求mod所以错了