CSP考试
第401题
若
，定义
；其中
对于给定自然数n0，存在序列n0,n1,n2,...,nm,其中对于
都有ni=f(ni-1)且nm=nm-1，称nm为n0关于f的不动点，问在10016至1A016中，关于f的不动点为9的自然数个数为（ ）。
第402题
现在用如下代码来计算xn,其时间复杂度为（）。
double quick_power(double x, unsigned n){
if(n == 0)return 1;
if(n == 1)return x;
return quick_power(x, n / 2)
* quick_power(x, n / 2)
*((n&1)?x:1);
}
第403题
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
当输入非零时，输出一定不为零。（）
第404题
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
将f函数的输入参数的类型改为 unsigned int，程序的输出不变。（）
第405题
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
当输入为“65535”时，输出为“63”。（）
第406题
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
当输入为“1”时，输出为“64”。（）
第407题
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
当输入为“512”时，输出为()。
第408题
2023年CSP-S1阅读程序题1：
#include <iostream>
using namespace std;
unsigned short f(unsigned short x){
x ^= x << 6;
x ^= x >>8;
return x;
}
int main(){
unsigned short x;
cin >> x;
unsigned short y = f(x);
cout << y <<endl;
return 0;
}假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：
当输入为“64”时，执行完第5行后x的值为(）。
第409题
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
将第15行删去，输出不变。（）
第410题
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
当输入为“10”时，输出的第一行大于第二行。（）
第411题
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
当输入为“1000”时，输出的第一行与第二行相等。（）
第412题
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
solve1(n)的时间复杂度为(）。
第413题
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
solve(2)的时间复杂度为（）。
第414题
2023年CSP-S1阅读程序题2：
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long solve1(int n){
vector<bool> p(n+1, true);
vector<long long> f(n+1,0),g(n+1,0);
f[1]= 1;
for (int i = 2; i*i <= n; i++){
if (p[i]){
vector<int> d;
for(int k = i;k <=n; k *= i)d.push_back(k);
reverse(d.begin(),d.end());
for (int k:d){for (int j =k; j<=n;j += k){
if (p[j]){
p[j]= false;
f[j]= i;
g[j]= k;
}
}
}
}
}
for (int i = sqrt(n)+ 1; i <= n; i++){
if (p[i]){
f[i]= i;
g[i]= i;
}
}
long long sum = 1;
for(int i = 2; i <= n; i++){
f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);
sum += f[i];
}
return sum;
}
long long solve2(int n){
long long sum = 0;
for(int i= 1; i <= n; i++){
sum += i*(n / i);
}
return sum;
}
int main(){
int n;
cin >> n;
cout << solve1(n)<< endl;
cout << solve2(n)<< endl;
return 0;
}假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：
输入为“5”时，输出的第二行为（）。
第415题
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
将第24行的“m”改为“m-1”输出有可能不变，而剩下情况为少1。（）
第416题
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
将第22行的“g+(h-g)/2”改为“(h+g)>>1”，输出不变。（）
第417题
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
当输入为“572-451-3”，输出为“5”。（）
第418题
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
设a数组中最大值减最小值加1为A，则f函数的时间复杂度为（）。
第419题
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
将第10行中的“>”替换为“>=”，那么原输出与现输出的大小关系为（）。
第420题
2023年CSP-S1阅读程序题3：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool fo(vector<int>& a, int m, int k){
int s =0;
for(int i =0,j =0; i<a.size(); i++){
while (a[i]- a[j]>m)j++;
s += i -j;
}
return s >= k;
}
int f(vector<int>& a, int k){
sort(a.begin(), a.end());1
int g =0;
int h = a.back()- a[0];
while(g< h){
int m = g+(h -g)/ 2;
if(fo(a,m, k)){
h = m;
} else {
g = m+1;27 }28 }29
return g;31}32
int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){
cin >> a[i];
}
cout<< f(a,k)<< endl;
return 0
}假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：
当输入为“582-538-12”时，输出为（）。