题意:给你一个整数n,求所有n/k的值(k∈{1,2,3...,n,.......}).
题解:最简单的方法是用枚举1~sqrt(n),把除数和商放进set中,就能直接水过,但后来看其他人的题解了解到了一种新方法:分块.
1,2,3,4,5,6,7,8,9,10.
10,5,3,2,2,1,1,1,1,1.
从k=1开始枚举,我们发现每个n/k的值都会对应一个区间,那么我们可以利用n/(n/k)来得到这个区间的最右边,且下次枚举一定是从n/(n/k)+1开始的.
e.g:当k=5时,n/k=2,n/(n/k)=5(值为2的区间最右边),然后直接k=n/(n/k)+1=6开始,n/k=1,n/(n/k)=10,结束,记得要把0加进去.
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <stack> 7 #include <queue> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <unordered_set> 12 #include <unordered_map> 13 #define ll long long 14 #define fi first 15 #define se second 16 #define pb push_back 17 #define me memset 18 const int N = 1e6 + 10; 19 const int mod = 1e9 + 7; 20 using namespace std; 21 typedef pair<int,int> PII; 22 typedef pair<long,long> PLL; 23 24 int t; 25 int n; 26 vector<int> res; 27 int main() { 28 ios::sync_with_stdio(false); 29 cin>>t; 30 while(t--){ 31 cin>>n; 32 res.clear(); 33 res.pb(0); 34 for(int l=1,r;l<=n;l=r+1){ 35 r=n/(n/l); 36 res.pb(n/l); 37 } 38 sort(res.begin(),res.end()); 39 printf("%d\n",res.size()); 40 for(auto x:res){ 41 printf("%d ",x); 42 } 43 puts(""); 44 } 45 46 return 0; 47 }