POJ - 2100 Graveyard Design-白红宇

POJ - 2100 Graveyard Design

阅读量：7282 次

发布时间：2019-06-30

本文共 1124 字，大约阅读时间需要 3 分钟。

n虽然高达1e14，但是满足条件的s不会超过sqrt(n)。可以想到在O(sqrt(n))的复杂度下，

求一个[1,sqrt(n)]连续区间和为n的方案。

/**********************************************************            ------------------                          **   author AbyssalFish                                   ***********************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long ll;const int N = 1e3;int ans[N][2];//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif ll n; scanf("%I64d",&n); ll m = sqrt(n+0.5); ll sum = 0; int sz = 0; for(ll i = 1, j = 1; i <= m; i++){ sum += i*i; while(sum > n) { sum -= j*j; j++; } if(sum == n) { ans[sz][0] = j; ans[sz++][1] = i; } } printf("%d\n", sz); for(int i = 0; i < sz; i++){ printf("%d",ans[i][1]-ans[i][0]+1); for(int j = ans[i][0]; j <= ans[i][1]; j++){ printf(" %d", j); } puts(""); } return 0;}