A. 位数问题

思路

想要解决这道题目，需要知道一个小学五年级的数学知识（奇偶性），那就是：

• 奇数+奇数=偶数。
• 偶数+偶数=偶数。
• 奇数+偶数=奇数。

只要知道这个知识，那么这道题目就可以解决了，因为3是奇数，在每一位添上3时，若本来的数为奇数，那+3便为偶数，若本来的数为偶数，那+3便为奇数，那我们便可以推出一个公式，先设置两个数组f与g，f[i] 表示数字数位为i位时组出的偶数个3的数量， g[i] 表示数字位数为 i 位时，组出的奇数个3的数量，而公式为：

• f[i]=g[i-1]+f[i-1]*9。
• g[i]=f[i-1]+g[i-1]*9。

但是要注意，若到n位时公式则变成了：

• f[n]=g[n-1]+f[n-1]*8。

代码

#include<bits/stdc++.h>
using namespace std; 
const int N=1e3+10;
unsigned long long f[N],g[N];
int main(){
	freopen("bit.in","r",stdin);
	freopen("bit.out","w",stdout);
	int n;
	cin>>n;
	f[1]=9,g[1]=1;
    for(int i=2;i<=n;i++){
    	if(i<n){
    		f[i]=g[i-1]+f[i-1]*9;
            g[i]=f[i-1]+g[i-1]*9;
		}
    	else f[n]=g[n-1]+f[n-1]*8;
		f[i]%=12345,g[i]%=12345;
	}
    cout<<f[n];
    return 0;
}

这道题目在写的时候写了暴力，只拿了20分，下次要想一想AC的写法。

B. 先先的生日

思路

对于这道题目，我们可以想到用约数来解决这个问题，先用一个桶来标记a[i]出现的次数，再扫一遍约数过去，那怎么扫呢，首先，1~n扫一遍过去肯定会超时，但因为约数是成对的，所以我们可以通过这个方法来扫，若是约数，那就将计数器加这一对约数，注意：因为自己是不用自己拍自己的头的，所以最后的答案是计数器-1。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e6+10;
int a[N],st[M];
int main(){
	freopen("birth.in","r",stdin);
	freopen("birth.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		st[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		long long sum=0;
		for(int j=1;j<=a[i]/j;j++){
			if(a[i]%j==0){
			    sum+=st[j];
			    if(j!=a[i]/j) sum+=st[a[i]/j];
		    }
		}
		cout<<sum-1<<endl;
	}
    return 0;
}

这道题目在写的时候写了暴力，只拿了10分，下次要想一想AC的写法。

C. 小静的考验

思路

对于这道题目我们先从前往后遍历一遍，但是我们发现，还是要往前遍历，所以我们不妨从后往前遍历，就不用再往后遍历了，若不满足条件，那该分的份数为：

• (a[i]+a[i+1]-1)/a[i+1]。

我们再将该分的份数用sum存起来，最后再将

• cnt+=sum-1。
• a[i]/=sum。

即可，而cnt即等于我们的答案，初始化为0。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int main(){
	freopen("xiaojing.in","r",stdin);
	freopen("xiaojing.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		long long n,cnt=0;
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=n-1;i>=1;i--){
			if(a[i]>a[i+1]){
				long long sum=(a[i]+a[i+1]-1)/a[i+1];
				cnt+=sum-1;
				a[i]/=sum;
			}
		}
		cout<<cnt<<endl;
	}
    return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。

D. 超级感染

思路

这道题目就是一道快速幂，直接套快速幂模版就行了。

代码

#include<bits/stdc++.h>
using namespace std;
long long mod=100003;
long long qsm(long long a,long long b){
	long long sum=1;
	while(b){
		if(b&1) sum=(sum*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return sum;
}
int main(){
	freopen("super.in","r",stdin);
	freopen("super.out","w",stdout);
    long long m,n;
    cin>>m>>n;
    cout<<(qsm(m,n)%mod-m*qsm(m-1,n-1)%mod+mod)%mod;
    return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。