，每次v1.
# [NOIP2001 普及组] 数的计算
## 题目描述
我们要求找出具有下列性质数的个数（包含输入的正整数 $n$）。
先输入一个正整数 $n$（$n le 1000$），然后对此正整数按照如下方法进行处理：
1. 不作任何处理；
2. 在它的左边拼接一个正整数，但该正整数不能超过原数，或者是上一个被拼接的数的一半；
3. 加上数后，继续按此规则进行处理，直到不能再加正整数为止。
## 输入格式
一行，一个正整数 $n$（$n le 1000$）。
## 输出格式
一个整数，表示具有该性质数的个数。
## 样例 #1
### 样例输入 #1
```
6
```### 样例输出 #1
```
6
```## 提示
**【样例解释】**
满足条件的数为：$6$，$16$，$26$，$126$，$36$，$136$。
**【题目来源】**
NOIP 2001 普及组第一题
我们以4为例子来进行说明
4后面可以跟上1,2组成14,24
14后面跟不了,24可以跟上1组成124
再加上4本身就可以得到4的种类
即 14,24,124,4
而我们只要算出1,2的种类就可以加起来得到4的种类
因此，我们得到
f[1]=1
f[2]=2=f[1]+1
f[3]=2=f[1]+1
f[4]=4=f[1]+f[2]+1
f[5]=4=f[1]+f[2]+1
using namespace std;
int n;
int f[1001];//存每一位数的种类
int main(){
cin>>n;
for(int i=1;i<=n;i++){ //1-n的递推
for(int j=1;j<=i/2;j++){
f[i]+=f[j]; //每一位叠加，递推走起
}
f[i]++; //加上本身
}
cout<
2.
# [NOIP1998 提高组] 车站
## 题目描述
火车从始发站（称为第 $1$ 站）开出，在始发站上车的人数为 $a$，然后到达第 $2$ 站，在第 $2$ 站有人上、下车，但上、下车的人数相同，因此在第 $2$ 站开出时（即在到达第 $3$ 站之前）车上的人数保持为 $a$ 人。从第 $3$ 站起（包括第 $3$ 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 $(n-1)$ 站），都满足此规律。现给出的条件是：共有 $n$ 个车站，始发站上车的人数为 $a$ ，最后一站下车的人数是 $m$（全部下车）。试问 $x$ 站开出时车上的人数是多少？
## 输入格式
输入只有一行四个整数，分别表示始发站上车人数 $a$，车站数 $n$，终点站下车人数 $m$ 和所求的站点编号 $x$。
## 输出格式
输出一行一个整数表示答案：从 $x$ 站开出时车上的人数。
## 样例 #1
### 样例输入 #1
```
5 7 32 4
```
### 样例输出 #1
```
13
```
## 提示
对于全部的测试点，保证 $1 leq a leq 20$，$1 leq x leq n leq 20$，$1 leq m leq 2 times 10^4$。
本题重点：斐波那契数列。
规律
设第二站上下车人数为b。
经过几步计算，可以得到下表：
显然前两行都与前面的数有关，就猜测第三行也与前面的数有关，于是得到第四行。很明显可以发现第四行a的系数比第三行多11，b的系数比第三行少11。
所以不用管前两行，把第三行直接列出来就行了。方程：
//sum1表示a的系数，sum2表示b的系数
sum1[i]=sum1[i-1]+sum1[i-2]-1;//前两个的和-1
sum2[i]=sum2[i-1]+sum2[i-2]+1;//前两个的和+1
后续
算完这些，b也就能够根据a和m求出来了。
很显然，a*sum1[n-1]+b*sum2[n-1]=ma∗sum1[n−1]+b∗sum2[n−1]=m。
即b=(m-a*sum1[n-1])/sum2[n-1]b=(m−a∗sum1[n−1])/sum2[n−1]。
于是答案就是 a*sum1[x]+b*sum2[x]∗sum1[x]+b∗sum2[x]。
#include
using namespace std;
int sum1[25], sum2[25];
int main()
{
int a,n,m,x;
sum1[2] = 1; sum1[3] = 2;
cin >> a >> n >> m >> x;
for (int i = 4; i < n; i++) {
sum1[i] = sum1[i - 1] + sum1[i - 2] - 1;
sum2[i] = sum2[i - 1] + sum2[i - 2] + 1;
}
int b = (m - a * sum1[n - 1]) / sum2[n - 1];
cout << a * sum1[x] + b * sum2[x];
return 0;
}
3.
# [NOIP2001 普及组] 最大公约数和最小公倍数问题
## 题目描述
输入两个正整数 $x_0, y_0$，求出满足下列条件的 $P, Q$ 的个数：
1. $P,Q$ 是正整数。
2. 要求 $P, Q$ 以 $x_0$ 为最大公约数，以 $y_0$ 为最小公倍数。
试求：满足条件的所有可能的 $P, Q$ 的个数。
## 输入格式
一行两个正整数 $x_0, y_0$。
## 输出格式
一行一个数，表示求出满足条件的 $P, Q$ 的个数。
## 样例 #1
### 样例输入 #1
```
3 60
```
### 样例输出 #1
```
4
```
## 提示
$P,Q$ 有 $4$ 种：
1. $3, 60$。
2. $15, 12$。
3. $12, 15$。
4. $60, 3$。
对于 $100%$ 的数据，$2 le x_0, y_0 le {10}^5$。
**【题目来源】**
NOIP 2001 普及组第二题
前置知识
- 最大公约数（即 gcdgcd） 和最小公倍数（即 operatorname{lcm}lcm）的求法。
该题的关键点在于，两个数的积等于它们最大公约数和它们最小公倍数的积。公式表示为 atimes b=gcd(a,b) times operatorname{lcm}(a,b)a×b=gcd(a,b)×lcm(a,b)。设作为答案的两个数为 xx 和 yy，我们要使它们同时满足以下三个条件，并统计这样的 xx 和 yy 的个数（P,QP,Q 含义见题目描述）：
- x times y=P times Qx×y=P×Q
- gcd(x,y)=Pgcd(x,y)=P
- operatorname{lcm}(x,y)=Qlcm(x,y)=Q
我们可以枚举 xx，判断是否存在满足条件 11 的整数 yy（即，xx 能否被 P,QP,Q 的积整除）。满足第一个条件后，再分别判断当前的 x,yx,y 是否能够同时满足另外两个条件即可。显然，这种做法会超时。
考虑优化这个程序。我们其实并不需要枚举两次，因为对于不同的 x,yx,y ，交换它们的值一定可以得到另一组与之对应的解。因此，从 11 到 sqrt{Ptimes Q}P×Q 枚举一遍，每发现一组答案就将 ansans 的值加上 22 即可。
一组 x,yx,y 有对应解时有条件：x,yx,y 的值不同。如果它们相同，交换后并不能得到与之对应的另一组数。当 x=yx=y 时，易得 x=y=gcd(x,y)=operatorname{lcm}(x,y)x=y=gcd(x,y)=lcm(x,y)。 所以要对此进行特判，若 P,QP,Q 相等，这种情况就存在， ansans 里要减去 11。
一些代码实现技巧：
-
c++ 里有一个自带的求 gcdgcd 的函数叫 __gcd 。upd：现在 NOIP 已经可以使用了。
-
当积相同且 gcdgcd 相同时，operatorname{lcm}lcm 也一定相同，因此只需判断是否满足一、二两个条件即可。
AC代码：（应该是目前最短的）
#include
using namespace std;
long long m,n,ans;
int main(){
cin>>m>>n;
if(m==n) ans--;
n*=m;//把两数的积存入n中
for(long long i=1;i<=sqrt(n);i++){
if(n%i==0&&__gcd(i,n/i)==m) ans+=2;
}
cout<
评论区常见问题统一回答：
Q：gcdgcd 是什么？
A：是“最大公约数”的缩写。同理，operatorname{lcm}lcm 是“最小公倍数”的缩写。
Q：代码中为什么枚举到 sqrt{n}n？
A：前文提到，我们要避免重复，因此循环时只算 xle yx≤y 的情况。当 x=yx=y 时，x=sqrt{n}x=n。再使 xx 变大就会使 x>yx>y 了，计算会重复。
