C. Everyone is a Winner!

Codeforces Round #603 (Div. 2)

题目链接:https://codeforces.com/contest/1263/problem/C

题目描述:

题目

思路:

整除分块!!!!就是把每一个n/i的商相等分为一块,这一块的i的区间[l,r],同一个区间内的每一个n/i=n/l。i从1开始,所以l从1开始枚举,r为每一块的最大值r=n/(n/l),l为每一块的最小值(下一块的起始值l=r+1)。当i>n时一定会有n/i=0,所以cnt初始为1。

代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
const int maxn=1e7;
int a[maxn];
map<int,int>mp;
int main(){
    int t,n;
    #ifdef HH
    freopen("G:/input.txt","r",stdin);
    #endif // HH
    scanf("%d",&t);
    while(t--){
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        int cnt;
        cnt=1;                                   //按我这个写法,其实当cnt到达最终答案的时候
        for(int l=1,r;l<=n;l=r+1){        //for循环并不会给a[cnt]赋值,
            r=n/(n/l);                           //但因为每次循环都初始化a
            a[cnt++]=n/l;                    //所以a[cnt]=0
        }
        printf("%d\n",cnt);
        for(int i=cnt;i>=1;i--){
            printf("%d",a[i]);
            if(i>1)printf(" ");
        }
        printf("\n");
    }
    return 0;
}
Last modification:December 10th, 2019 at 09:17 pm
如果觉得我的文章对你有用,请随意赞赏