位数问题c++

本文主要是介绍位数问题c++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

在所有的N位数中，有多少个数中有偶数个数字3，由于结果可能很大，你只需要输出这个答案对12345取余的值。

输入

读入一个数N(N≤1000)

输出

输出有多少个数中有偶数个数字3。

样例输入

2

样例输出

73

样例解释：

10 11 12 14 15 16 17 18 19 20 21 22 24 25 26 27 28 29 33 40 41 42 44 45 46 47 48 49 50 51 52 54 55 56 57 58 59 60 61 62 64 65 66 67 68 69 70 71 72 74 75 76 77 78 79 80 81 82 84 85 86 87 88 89 90 91 92 94 95 96 97 98 99

以上73个数据吻合样例要求

分析： 

首先我们可以用a数组来表示：n位数中有多少个数中有偶数个数字3，用b数组来表示：n位数中有多少个数中有奇数个数字3

那么可以得出：

a[1]=8;

b[1]=1;

a[2]=73;

b[2]=17;

等等。

根据推理我们可以发现规律：

便可得出答案

而且为了防止数据过大，应在循环里加上%12345

 代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,a[1001],b[1001];
int main(){cin>>n;a[1]=8;b[1]=1;for(int i=2;i<=n;i++){a[i]=a[i-1]*9+b[i-1];b[i]=a[i-1]+b[i-1]*9;a[i]%=12345;b[i]%=12345;}cout<<a[n];return 0;
}

这篇关于位数问题c++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---