T1位数问题

思路：

这道题题要用奇偶的性：

• 偶+偶=偶；
• 奇+奇=偶；
• 偶+奇=奇；

要计算奇数与偶数的数量。

一位数时

偶数有9 ； 奇数有1；

放3： 组成偶数：上一位能组出1个奇数，就是1个

组成奇数：上一位能组成9个偶数，就是9个

不放3：9×9 = 81 组成偶数：上一位能组出9个偶数，就是9× 9=81个

组成奇数：上一位能组成1个奇数，就是9×1=9个

定义两个数组 f[N],g[N]

f[i] 表示数字数位为 i 位时，组出的偶数个3的数量

g[i] 表示数字位数为 i 位时，组出的奇数个3的数量

规律：

f[i] = 上一次组出的奇数 + 上一次组出的偶数×9 g[i] = 上一次组出的偶数 + 上一次组出的奇数×9

$$f[i] = g[i-1] + f[i-1]*9$$ $$g[i] = f[i-1] + g[i-1]*9$$

注意：

$f[1]=1;$

$g[1]=9;$ 还有推到最高位的时候，要乘8。

代码

#include<bits/stdc++.h>
using namespace std;
const int MOD=12345,N=1e4+10;
long long n,cnt,f[N],g[N];
int main(){
	cin>>n;
	f[1]=9;
	g[1]=1;
	for(int i=2;i<=n;i++){
		f[i]=f[i-1]*9+g[i-1];
		g[i]=g[i-1]*9+f[i-1];
		f[i]%=MOD;
		g[i]%=MOD;
	}
	f[n]=f[n-1]*8+g[n-1];
	g[n]=g[n-1]*8+f[n-1];
	f[n]%=MOD;
	g[n]%=MOD;
	cout<<f[n];
	return 0;
}

T2先先的生日

思路：

对于这道题目，我们可以用约数来解决。 先用一个桶来标记a[i]出现的次数，再用每个数的约数扫过去，加上对应的a[i];

注意：

• 因为自己不用算还要减1；
• 如果约数等于a[i]数除以它的话（例如：2=4÷2），就只要加一次。

关键代码

for(int i=1;i<=n;i++){
		int x=a[i],ans=0;
		for(int j=1;j<=x/j;j++){
			if(x%j==0){
				if(j!=x/j){
					ans=ans+cnt[j]+cnt[x/j];
				}else{
					ans=ans+cnt[j];	
				}
			}
		}
		cout<<ans-1<<endl;
	}