每日一题AC

4.小花和小草正在沙滩上玩挖沙洞的游戏。他们划了一条长度为n米的线作为挖沙洞的参考线路，小花和小草分别从两头开始沿着划好的线开始挖洞，小花每隔a米挖一个洞，小草每隔b米挖一个洞，碰到已经挖过洞的就不需要再挖了。那么，你能帮小花和小草算算，他们全部挖到头之后，一共挖了多少个洞吗?(两头端点位置都要挖洞)

输入格式 第1行:一个正整数n,代表线路的长度。(3<=n<=10000) 第2行:用空格分隔的两个正整数,代表a和b的值。(1<=a,b<=50)

输出格式 输出1行：1个整数，表示最终挖出来的沙洞的个数。

输入输出样列 输入样例1： 6 23 输出样例1： 5 输入样例2： 100 5 10 输出样例2： 21

思路： 如果ka=n-qb（0<=k,q），那么这个洞就重复了。计算两个人在路上应该挖的洞减去重复挖的洞。

AC代码：

#include<stdio.h>
int main()
{int n;int a,b;scanf("%d",&n);scanf("%d%d",&a,&b);int k=0,m=0;int count=n/a+n/b+2;for(k=1;k<=n/a;k++){for(m=1;m<=n/b;m++){if(a*k==n-m*b){count--;}}}printf("%d\n",count);
​
}

给定线路长度n，以及小花和小草挖洞的间隔a和b，计算最终挖出来的沙洞的个数。
​
程序首先读取输入的n、a和b。然后初始化计数器count为n/a+n/b+2，表示最初能够挖到的洞的个数，加2是因为两头的端点位置也要挖洞。
​
接下来是两重循环，外层循环遍历从1到n/a的所有可能取值k，内层循环遍历从1到n/b的所有可能取值m。对于每一组k和m的取值，判断ak是否等于n-mb。如果相等，说明这是一处已经挖过的洞，count减1。
​
最后，输出答案count。
​
该程序的时间复杂度为O(n/a*n/b)，其中a和b为输入的整数。

网上代码：

#include<iostream>
using namespace std;
​
typedef long long ll;
​
int main()
{ll n,a,b;int cnt_a=0;int cnt_b=0;ll ans=0;cin>>n>>a>>b;cnt_a=n/a;cnt_b=n/b;ans+=cnt_a+cnt_b+2;
​if(a==1||b==1) cout<<n+1<<endl;else for(int i=0;i<=cnt_a;i++){for(int j=0;j<=cnt_b;j++){if(i*a+j*b==n){ans--;}else if(i*a+j*b>n){//怕超时，剪枝break;}}}
​cout<<ans<<endl;
​return 0;
}
​

这段代码是一个求解整数拆分问题的程序。给定一个整数n以及两个整数a和b，要求将n拆分成若干个数相加的形式，使得其中包含至少一个a和至少一个b，计算不同的拆分方式总数。
​
程序首先读取输入的n、a和b，然后初始化计数器cnt_a和cnt_b为0，用于记录a和b在拆分中出现的次数。同时，初始化答案ans为0，用于记录不同的拆分方式总数。
​
程序接着计算cnt_a和cnt_b，分别为n除以a和n除以b的商，表示a和b在拆分中最多可以出现的次数。
​
然后，答案ans加上cnt_a和cnt_b，再加2，表示拆分中至少包含一个a和一个b的情况。
​
接下来是一个双重循环，外层循环遍历从0到cnt_a的所有可能取值i，内层循环遍历从0到cnt_b的所有可能取值j。对于每一组i和j的取值，判断ia+jb是否等于n。如果等于n，则说明这是一种有效的拆分方式，ans减1。如果ia+jb大于n，则跳出内层循环，进行下一组i和j的取值。
​
最后，输出答案ans。
​
该程序的时间复杂度为O(n/a*n/b)，其中a和b为输入的整数。