A27713. 除法(divide)问题描述小可可进入了小学三年级，开始学习除法，一开始学习余数为 0 的除法，后来又学习了余数不为 0 的除法。小可可数学很好，对被除数、除数、商、余数都弄得很清楚。有一天，他在思考这样的一个问题：给一个正整数 n 作为被除数，除数 k 可以取任意正整数，那么商有多少个不同的值呢？例如：被除数 n=5，无论除数 k 取任何正整数，商只有 4 个不同的值，分别为 0, 1,2, …
填空题
中等
知识点
题目描述
除法(divide)
问题描述
小可可进入了小学三年级，开始学习除法，一开始学习余数为 0 的除法，后来又学习了余数不为 0 的除法。
小可可数学很好，对被除数、除数、商、余数都弄得很清楚。有一天，他在思考这样的一个问题：给一个正整数 n 作为被除数，除数 k 可以取任意正整数，那么商有多少个不同的值呢？
例如：被除数 n=5，无论除数 k 取任何正整数，商只有 4 个不同的值，分别为 0, 1,2, 5，因为 5÷6 = 0…5，5÷5=1…0，5÷4=1…1，5÷3=1…2,
5÷2=2…1，5÷1=5…0。
小可可最近有点忙，他把这个问题交给了你。
输入格式
本题有多组测试数据。
第一行输入一个整数 T，表示测试数据的组数。
接下来 T 行，每行一个整数 n，表示被除数。
输出格式
输出 2*T 行，对于每组测试数据输出 2 行：
第 1 行输出一个整数 m，表示商有 m 个不同的值；
第 2 行输出 m 个整数，分别表示这 m 个不同的值，按从小到大的顺序输出，两个数之间保留一个空格。
输入输出样例 1
输入
2
5
11
输出
4
0 1 2 5
6
0 1 2 3 5 11
数据范围
对于 50%的数据满足：1≤ n ≤10^5。
对于 100%的数据满足：1≤ T ≤10，1≤ n ≤10^9。
参考答案
/*
由题意可知,0必定是商之一
对于正整数K,只需要遍历0~sqrt(K)即可
设1<=i<=(int)sqrt(K),分别将K/i和K/(K/i)的值存入数组ans[0]和ans[1]
然后从小到大输出
*/
#include<bits/stdc++.h>
using namespace std;
int ans[2][100000];
//ans[0]从小到大存商
//ans[1]从大到小存商
int main(){
int T;
cin>>T;
while(T--){
memset(ans,0,sizeof(ans));
int n;
cin>>n;
int p=0,q=-1;//ans[0][0]存的商为0的情况
for(int i=1;i*i<=n;i++){
int temp=n/i;
if(n/i==n/temp){//商出现重叠，遍历结束break
ans[0][++p]=temp;
break;
}else{
ans[0][++p]=i;
ans[1][++q]=temp;
}
}
cout<<p+q+2<<endl;//考虑ans[0][0]和ans[1][0]两个商，所以+2
for(int i=0;i<=p;i++)//正向输出
cout<<ans[0][i]<<" ";
for(int j=q;j>=0;j--)//反向输出
cout<<ans[1][j]<<" ";
cout<<endl;
}
}
上一题
下一题