[POI 20 Stage 3] Where is the one?

作法：

首先可以推出第二種詢問只需要一次就夠了，因為如果暴力枚舉排列中的兩個數，然後用 1 ~ n-1 去試是否整除他，就可以知道哪些數是相差1的，那麼只有一個數和他相差 1 的數就是 1 或 n 了，再問問看這兩個數誰比較大就可以了。所以問題轉化為求出 n 和 1 所在的位置。

因為第一種詢問就等價於問「兩個數是否模 d 同餘」，所以如果我們想求出 1 ~ n 中 1 和 n 的位置，考慮把這些數按照模 2 分成兩坨，如果有一坨的個數比另一坨多，那麼最大和最小數一定在比較多的那坨裡面，否則我們可以分別對兩邊遞回下去，求出最大和最小的數，最後再看看到底哪兩個數才是所求的最大最小數就好了，而這只要拿 n-1 去問兩數是否同餘就好了。具體來說，我們在遞回的時候的子問題是「已知有一些位置的數滿足他們全部都模 d 同餘，且已知最大和最小的差是 m ，要求出最大和最小的數落在哪個位置」，而剛剛考慮的「模 2 分成兩坨」只要改成「模 2 * d 分成兩坨」就好了，並且最後再確認哪兩個數是最大最小數的時候是用 m 去問他們是否同餘。

code :

#include<bits/stdc++.h>
#include"cgdzlib.h"
using namespace std;
const int maxn=500000+10 ;
 
vector<int> v[4*maxn] ;
int vcnt=0 ;
 
void solve(const vector<int> &vec,int d,int m,int &mi,int &ma)
{
    if(vec.size()==2) { mi=vec[0] ; ma=vec[1] ; return ; }
    v[vcnt].push_back(vec[0]) ;
    for(int i=1;i<vec.size();i++)
    {
        if(f(vec[i],vec[0],2*d)) v[vcnt].push_back(vec[i]) ;
        else v[vcnt+1].push_back(vec[i]) ;
    }
    int tmp=vcnt ; vcnt+=2 ;
    if(v[tmp].size()!=v[tmp+1].size())
    {
        if(v[tmp].size()>v[tmp+1].size())
            solve(v[tmp],2*d,m,mi,ma) ;
        else
            solve(v[tmp+1],2*d,m,mi,ma) ;
        return ;
    }
 
    int a[2],b[2] ;
    solve(v[tmp],2*d,m-d,a[0],a[1]) ;
    solve(v[tmp+1],2*d,m-d,b[0],b[1]) ;
    for(int i=0;i<2;i++) for(int j=0;j<2;j++)
        if(f(a[i],b[j],m))
    {
        mi=a[i] ; ma=b[j] ;
        return ;
    }
}
 
main()
{
    int n=inicjuj() ;
    if(n==1) odpowiedz(1) ;
 
    for(int i=1;i<=n;i++) v[0].push_back(i) ;
    vcnt++ ;
    int a,b ;
    solve(v[0],1,n-1,a,b) ;
    if(g(a,b)) odpowiedz(b) ;
    else odpowiedz(a) ;
}
 

[POI 20 Stage 3] Colorful Chain

作法：

經典題，用滑動窗口 + 維護目前這個區間中的每個數字的個數，還有維護目前有幾個「某數字出現的次數」是正確的，當全部的數字出現的次數都是正確的話就是OK的，否則就不是。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
int getint()
{
    char c=getchar() ;
    while(c<'0'||c>'9') c=getchar() ;
    int x=0 ;
    while(1)
    {
        x=x*10+(c-'0') ;
        c=getchar() ;
        if(c<'0'||c>'9') return x ;
    }
}
 
int a[maxn],num[maxn],cnt=0 ;
int tmp[maxn];
 
void add(int x,int val)
{
    bool b1=(num[x]==0) ;
    num[x]-=val ;
    bool b2=(num[x]==0) ;
    if(b1 && !b2) cnt-- ;
    if(!b1 && b2) cnt++ ;
}
 
main()
{
    int n=getint(),m=getint() ; LL k=0LL ;
    for(int i=1;i<=m;i++) tmp[i]=getint() , k+=tmp[i] ;
    for(int i=1;i<=m;i++)
    {
        int x=getint() ;
        num[x]=tmp[i] ;
    }
    for(int i=1;i<=n;i++) a[i]=getint() ;
 
    if(k>n) { printf("0\n") ; return 0 ; }
 
    int ans=0 ;
    for(int i=1;i<k;i++) add(a[i],1) ;
    for(int i=k;i<=n;i++)
    {
        add(a[i],1) ;
        if(cnt==m) ans++ ;
        add(a[i-k+1],-1) ;
    }
    printf("%d\n",ans) ;
}
 

[POI 20 Stage 3] Bytecomputer

作法：

DP，設 dp[ i ][ 0 ~ 2 ] 代表只考慮 a_1 ~ a_i ，要把 a_i 加成 -1 or 0 or 1 的最小花費，分情況討論即可。

code :

#include<bits/stdc++.h>
#define INF 1000000000
#define MIN(x,y,z) min(min(x,y),z)
using namespace std;
const int maxn=1000000+10 ;
 
int dp[maxn][3] ;
int a[maxn] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    for(int i=0;i<3;i++) dp[1][i]= ( a[1]==i-1 ? 0 : INF ) ;
    for(int i=2;i<=n;i++)
    {
        if(a[i]==1)
        {
            dp[i][2]=MIN(dp[i-1][0],dp[i-1][1],dp[i-1][2]) ;
            dp[i][1]=dp[i-1][0]+1 ;
            dp[i][0]=dp[i-1][0]+2 ;
        }
        else if(a[i]==0)
        {
            dp[i][2]=dp[i-1][2]+1 ;
            dp[i][1]=min(dp[i-1][0],dp[i-1][1]) ;
            dp[i][0]=dp[i-1][0]+1 ;
        }
        else
        {
            dp[i][2]=dp[i-1][2]+2 ;
            dp[i][1]=INF ;
            dp[i][0]=dp[i-1][0] ;
        }
    }
    int ans=MIN(dp[n][0],dp[n][1],dp[n][2]) ;
    if(ans>2*n) printf("BRAK\n") ;
    else printf("%d\n",ans) ;
}
 

[POI 20 Stage 3] Tower Defense game

這題蠻有梗的XD 一開始看看起來好難，結果沒想到很簡單XD

作法：

關鍵在於他沒有要求最佳解，而是給一個 k 滿足存在一個 k 個點的點集 P，使得每個點要嘛在點集裡面，要嘛有一個鄰居在點集裡面。有了這個條件，我們只要從 1 開始檢查，如果有一個點還沒被蓋到就直接在他的位置放上強力守衛，這樣就可以在 <= k 次放置內蓋完全部的點了。而證明也不難，因為對於一個還沒被蓋到的點，一定是他落在 P 裡面或是他有一個鄰居落在 P 裡面，所以當在這個點放上強力守衛後，會等價於這個點和所有這個點的鄰居都有了一個一般的守衛，這樣顯然會比只有其中一個點有守衛的情況好，所以當然可以在 k 次以內達到。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10 ;
 
vector<int> v[maxn] ;
bool vis[maxn] ;
vector<int> ans ;
main()
{
    int n,m,k ; scanf("%d%d%d",&n,&m,&k) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    for(int i=1;i<=n;i++) if(!vis[i])
    {
        ans.push_back(i) ; vis[i]=1 ;
        for(int j=0;j<v[i].size();j++)
        {
            int x=v[i][j] ; vis[x]=1 ;
            for(int k=0;k<v[x].size();k++) vis[v[x][k]]=1 ;
        }
    }
    printf("%d\n",ans.size()) ;
    for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i+1==ans.size()?'\n':' ') ;
}
 

[POI 21 Stage 3] Solar Panels

作法：

題目簡單來說就是對於一個矩形的區域，問這個區域裡 x 坐標根 y 坐標的 gcd 的最大值是多少。考慮一個樸素的算法：枚舉一個數 d 當 gcd ，看看這個區域裡面是否有一個點滿足他的 x 坐標和 y 坐標都是 d 的倍數，接下來要改進這個算法。

假設矩形的左下角叫 ( x0 , y0 )，右上角叫 ( x1 , y1 ) ，那麼當左下角和 d 確定之後，最有可能落在詢問矩形內的兩坐標都是 d 的倍數的數也就確定了，他的 x 坐標就是 >= x0 的第一個 d 的倍數， y 坐標同理。以下記 L1 = x1 - x0 ， L2 = y1 - y0 。因為>= x0 的第一個 d 的倍數和 x 的差會等於 d - ( ( x0 - 1 ) % d ) - 1，所以這個數 <= x1 的充要條件就是 d - ( ( x0 - 1 ) % d ) - 1 <= L1　，或是　( x0 - 1 ) % d >= d - L1 - 1 。y 坐標同理有 ( y0 - 1 ) % d >= d - L2 - 1，所以 d 是一個可行的 gcd 若且唯若上面兩條式子成立。

再來要用到一個神奇的取餘數的性質，就是當 a / b = q 且 a % b = r 時，如果 b 增加 1 並且保持他們的商 q 不變的話，那麼餘數就會減少 q 。因為 a = b * q +r = ( b + 1 ) * q + ( r - q )。為了使用這個性質，我們還需要知道 b 最大可以到多大( 還能夠保持和 a 相除的商是 q  )。設 b 的最大值為 x 好了，因為 a / x = q，所以必須要有 q * x <= a < ( q +1 ) * x ，可以推出 x = a / q 。所以 b 可以到達的最大數就是 a / q = a / ( a / b ) 。這東西也在 POI 14 Stage 1 Queries ( HOJ 22 駭客 ) 出現過，可以參考看看這裡。

這樣一來，記 d2 = min( ( x0-1 ) / (( x0-1 )/d) , ( y0-1 ) / ((y0-1)/d) )，就會得到在 d ~ d2 之間上面那兩條式子的左邊的變動會是線性的。具體來說，設 x0-1 = d * q1 + r1 ，那麼當 d 增加為 d +x 的時候，新的商還是一樣是 q1 ，但新的餘數就會變成 r1 - x * q1 ，而我們希望的是 ( x0 - 1 ) % (d+x) >= (d+x) - L1 - 1 ，其中 d +x 越大越好，現在已經知道左式等於 r1 - x * q1 了，所以移項一下得到 x 必須滿足 ( q1 +1 ) x <= r1 + L1 +1 - d ，同理設 y0-1 = d * q2 + r2 ，那麼 x 也必須滿足 ( q2 +1 ) x <= r2 + L2 +1 - d ，再加上先天的條件 x <= d2 - d ，就可以得到在 d ~ d2 之間最佳的答案是多少了，用他去更新答案即可。

另外在實作上要注意的小細節是，在計算 d2 的時候可能有一邊會變成除以 0 ，這時只要特判讓它變成一個很大的數就好了，反正等一下取 min 就會把它弄掉了 ( 不可能兩數都變成除以0 )。

code :

#include<bits/stdc++.h>
#define INF 1100000000
using namespace std;
 
int divi(int x,int y)
{
    return y==0 ? INF : x/y ;
}
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int x0,L1,y0,L2 ;
        scanf("%d%d%d%d",&x0,&L1,&y0,&L2) ;
        L1-=x0 ; L2-=y0 ;
        int ans=1 ;
        for(int d=1;d<=x0 || d<=y0;)
        {
            int d1=min( divi(x0-1,(x0-1)/d) , divi(y0-1,(y0-1)/d) ) ;
            int q1=(x0-1)/d , r1=(x0-1)%d ;
            int q2=(y0-1)/d , r2=(y0-1)%d ;
            if(r1+L1+1>=d && r2+L2+1>=d)
            {
                int x=d1-d ;
                x=min(x, (r1+L1+1-d)/(q1+1) ) ;
                x=min(x, (r2+L2+1-d)/(q2+1) ) ;
                ans=max(ans,d+x) ;
            }
            d=d1+1 ;
        }
        printf("%d\n",ans) ;
    }
}
 

[POI 21 Stage 3] FarmCraft

作法：

以下記每個點安裝的時間為 t[ i ]。記 dp[ u ]代表目前在 u ，並且要讓 u 的所有子節點都安裝完成的最少時間。那麼第一個要考慮的就是 u 花的時間，如果 u 不是 1 ，那麼就是 t[ u ] ，否則就是 2 * ( n - 1 ) + t[ u ] 。再來則是要依序完成 u 的子樹們，對於每個子樹，我們需要的資訊有「從 u 走進去走完一圈再出來的時間」和「子樹完成安裝的時間」，後者顯然就是子樹的 dp 值，而前者則不難證明就是子樹的大小 * 2 。所以這個問題就等價於：現在有 m 個工作，每個工作有交代時間 ( 子樹的大小 * 2 ) 和執行時間 ( 子樹的 dp 值 )，必須交代完一個工作才能交代下一個工作，並且從交代的那一刻開始執行，求所有工作執行結束的最少時間。而這就是經典的 greedy ，因為可以把「從交代的那一刻開始執行」改成「從交代完再開始執行，執行 (子樹 dp 值 - 子樹大小 * 2 ) 的時間」，所以只要按照轉換後的執行時間由大到小排序，依序完成每個子樹就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10 ;
 
struct P
{
     int id,val ;
     bool operator < (const P &rhs) const
     {
          return val>rhs.val ;
     }
} tmp[maxn] ;
 
vector<int> v[maxn] ;
int t[maxn],sz[maxn],dp[maxn] ;
 
void dfs(int x,int f)
{
     sz[x]=1 ;
     if(v[x].size()==1 && x!=1) { dp[x]=t[x] ; return ; }
     for(int i=0;i<v[x].size();i++) if(v[x][i]!=f)
          dfs(v[x][i],x) , sz[x]+=sz[v[x][i]] ;
     int cnt=0 ;
     for(int i=0;i<v[x].size();i++) if(v[x][i]!=f)
          tmp[cnt++]=(P){v[x][i],dp[v[x][i]]-2*sz[v[x][i]]} ;
     sort(tmp,tmp+cnt) ;
 
     int ret= (x==1 ? 2*(sz[x]-1)+t[x] : t[x]) ;
     for(int i=0 , sum=0;i<cnt;i++)
     {
          ret=max(ret,sum+1+dp[tmp[i].id]) ;
          sum+=2*sz[tmp[i].id] ;
     }
     dp[x]=ret ;
}
 
main()
{
     int n ; scanf("%d",&n) ;
     for(int i=1;i<=n;i++) scanf("%d",&t[i]) ;
     for(int i=1;i<n;i++)
     {
          int x,y ; scanf("%d%d",&x,&y) ;
          v[x].push_back(y) ;
          v[y].push_back(x) ;
     }
     dfs(1,1) ;
     printf("%d\n",dp[1]) ;
}
 

[POI 21 Stage 3] Ant colony

作法：

直接模擬的話顯然會TLE，但其實可以注意到在模擬的過程中，對於某個特定的葉子只有落在一個特定範圍內的組員數量才有辦法在走到目標通道的時候剩下 k 隻。所以我們可以對目標通道的兩個端點分別往下DP，對每個點算出「在這個點時要有幾隻到幾隻的螞蟻，才可以在走到目標通道時剩下 k 隻」，最後再去對每個葉子看給定的 m_i 裡面有幾個數介於那個點的區間之間。

code :

#include<bits/stdc++.h>
#define INF 2000000000
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
int mul(int x,int y)
{
     if(INF/y < x) return INF ;
     return x*y ;
}
 
vector<int> v[maxn] ;
int g[maxn] ;
 
int dp1[maxn],dp2[maxn] ;
 
void dfs(int x,int f)
{
     if(v[x].size()==1)
     {
          dp1[x]=dp1[f] ;
          dp2[x]=dp2[f] ;
          return ;
     }
     int d=v[x].size() ;
     dp1[x]=mul(d-1,dp1[f]) ;
     dp2[x]=mul(d-1,dp2[f]+1)-1 ;
     for(int i=0;i<v[x].size();i++) if(v[x][i]!=f)
          dfs(v[x][i],x) ;
}
 
int m ;
int cal(int x,int y)
{
     int id1=lower_bound(g+1,g+m+1,x)-g ;
     int id2=upper_bound(g+1,g+m+1,y)-g ;
     return id2-id1 ;
}
 
main()
{
     int n,k ; scanf("%d%d%d",&n,&m,&k) ;
     for(int i=1;i<=m;i++) scanf("%d",&g[i]) ;
     sort(g+1,g+m+1) ;
 
     int st1,st2 ;
     for(int i=1;i<n;i++)
     {
          int x,y ; scanf("%d%d",&x,&y) ;
          if(i==1) st1=x , st2=y ;
          else v[x].push_back(y) , v[y].push_back(x) ;
     }
 
     if(v[st1].empty()) dp1[st1]=dp2[st1]=k ;
     else dp1[st1]=mul(k,v[st1].size()) ,
          dp2[st1]=mul(k+1,v[st1].size())-1 ;
     if(v[st2].empty()) dp1[st2]=dp2[st2]=k ;
     else dp1[st2]=mul(k,v[st2].size()) ,
          dp2[st2]=mul(k+1,v[st2].size())-1 ;
 
     for(int i=0;i<v[st1].size();i++) dfs(v[st1][i],st1) ;
     for(int i=0;i<v[st2].size();i++) dfs(v[st2][i],st2) ;
 
     LL ans=0LL ;
     v[st1].push_back(st2) ; v[st2].push_back(st1) ;
     for(int i=1;i<=n;i++) if(v[i].size()==1)
          ans+=cal(dp1[i],dp2[i]) ;
     printf("%lld\n",ans*k) ;
}
 

[POI 19 Stage 2] Fibonacci Representation

作法：

大概可以想的到是某種貪心。當給定一個 n 時，若 n 是某個 F_x ，那麼答案當然是 1 。否則令 F_x < n < F_(x+1) ，那麼最佳的取法就是取 +F_x 或是 +F_(x+1) ，這樣就只需湊出 n - F_x 或是 F_(x+1) - n ，取兩者之中比較小的那個一直做下去就可以了。

這個作法看起來很合理，這裡給一個大概的證明：

之後的證明會用到以下幾個引理：
1. 最佳的取法中不會出現 +F_x 和 +F_(x+1) 。2. 最佳的取法中不會出現 +F_x 和 -F_(x-1) 。
3. 最佳的取法中不會出現 +F_x 和 -F_(x-2) 。

4. F_x >= F_(x-1) + F_(x-3) + ... 。

其中 1~3 是顯然的，而 4 可以把 F_(x-1) 搬到左邊消掉然後數歸下去。

第一個要證明的是為什麼取 +F_x 或是 +F_(x+1)是最好的。如果取 +F_(x+2) 的話，由前面的引理知道不會取 +F_(x+1) 或是 -F_(x+1) ，也不會取 -F_x，這樣一來能得到的最小數就會是 F_(x+2) - F_(x-1) - F_(x-3) - ... >= F_(x+2) - F_x = F_(x+1) > n ，矛盾。如果取的是 > F_(x+2) 的數的話一樣可以推到矛盾。又如果取的是 F_(x-1) 或更小的數的話，能得到的最大樹就會是 F_(x-1) + F_(x-3) + ... <= F_x < n ，矛盾。所以取 F_x 或是 F_(x+1) 會是最好的。

再來則是為什麼 n - F_x 和 F_(x+1) - n 之中比較小的那個數可以用比較少個 F 湊出來。注意到這兩數相加 = F_(x-1) ，所以這件事會等價於：有兩個數 n , m ，滿足 n +m = F_k  且 n < m，則 n 可以用比較少個 F 湊出來。這只要注意到：因為 2*m > F_k = F_(k-1) +F_(k-2) > 2*F_(k-2) ，所以 m > F_(k-2) ，也就是組成 m 的最大的 F 值只可能是 F_(k-2) , F_(k-1) 或 F_k ，那麼考慮把 m 的組成直接用 F_k 減掉，並且如果 m 最高位是 F_k 的話直接消掉，如果不是的話就把 F_k 改成 F_(k-1) + F_(k-2) 根其中一個消掉，這樣我們得到了 n 的一個拆法，它拆出來的個數會 <= m 拆出來的個數，得證。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
LL F[100] ;
main()
{
    F[1]=F[2]=1 ;
    for(int i=3;i<100;i++) F[i]=F[i-1]+F[i-2] ;
    int T; scanf("%d",&T) ;
    while(T--)
    {
        LL x ; scanf("%lld",&x) ;
        int ans=0 ;
        while(x)
        {
            int i ;
            for(i=1;F[i]<x;i++) ;
            ans++ ; x=min(F[i]-x,x-F[i-1]) ;
        }
        printf("%d\n",ans) ;
    }
}
 

[POI 19 Stage 2] Cloakroom

作法：

首先把問題轉換成：給定一些線段，每條線段有他自己的價值，每次詢問一個區間，問在所有包含這個區間的線段中能不能用他們的價值湊出給定的價值。

假設現在的詢問是 [ L , R ] ，問能不能湊出 C ，那麼可以發現：如果詢問的 R 值變得越來越小，會讓可以湊出 C 的可能性越來越高(因為有更多的線段包含了詢問的區間)，所以我們可以對一個價值 C 只記錄他的臨界點，代表詢問的區間右端點 <= 這個臨界點的時候是有辦法湊出 C 的，否則就是沒辦法。所以我們考慮離線處理所有詢問，按照詢問的左端點由小到大排序，每次作下一個詢問的時候，先把所有線段左端點 <= L 的線段拿去更新剛才的臨界點陣列，然後直接查詢詢問價值的臨界點是否 >= 詢問的區間右端點即可。


code :

#include<bits/stdc++.h>
#define INF 1100000000
using namespace std;
const int maxn=1000+10 , maxq=1000000+10 , maxc=100000+10 ;
 
struct P
{
    int l,r,c,id;
    bool operator < (const P &rhs) const
    {
        return l==rhs.l ? r<rhs.r : l<rhs.l ;
    }
}a[maxn],q[maxq] ;
 
int dp[maxc] ;
bool ans[maxq] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].c,&a[i].l,&a[i].r) ;
    int Q ; scanf("%d",&Q) ;
    for(int i=1;i<=Q;i++)
        scanf("%d%d%d",&q[i].l,&q[i].c,&q[i].r) ,
        q[i].id=i ,
        q[i].r+=q[i].l+1 ;
 
    sort(a+1,a+n+1) ; sort(q+1,q+Q+1) ;
    dp[0]=INF ;
    for(int i=1,j=1;i<=Q;i++)
    {
        while(j<=n && a[j].l <= q[i].l)
        {
            for(int k=maxc-1;k>=a[j].c;k--)
                dp[k]=max(dp[k],min(dp[k-a[j].c],a[j].r)) ;
            j++ ;
        }
        ans[q[i].id]= (q[i].r<=dp[q[i].c] ? 1 : 0) ;
    }
    for(int i=1;i<=Q;i++) printf("%s\n",ans[i]?"TAK":"NIE") ;
}
 

[POI 19 Stage 2] Vouchers

作法：

直接模擬就可以了，對每個 x 要記錄一個 st[ x ] ，代表 x 的倍數裡面從 x 到 st[ x ] 大小的糖果包都已經被拿走了。還有當拿的糖果包大小 > 1000000 的時候就可以直接跳掉了，因為不影響哪些人拿到有裝神祕禮物的糖果包，這樣就可以保證複雜度是 O( C * logC ) 了，其中 C 是數字的最大值。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
int vis[maxn],st[maxn] ;
vector<LL> ans ;
main()
{
     int n ; scanf("%d",&n) ;
     while(n--)
     {
          int x ; scanf("%d",&x) ;
          vis[x]=1 ;
     }
     scanf("%d",&n) ;
     LL cnt=0 ;
     while(n--)
     {
          int x ; scanf("%d",&x) ;
          int i=st[x]+x ;
          for(int j=1;j<=x && i<maxn;i+=x)
          {
               if(vis[i]==2) continue ;
               if(vis[i]==1) ans.push_back(cnt+j) ;
               vis[i]=2 ; j++ ;
          }
          st[x]=i-x ;
          cnt+=x ;
     }
     printf("%d\n",ans.size()) ;
     for(int i=0;i<ans.size();i++) printf("%lld\n",ans[i]) ;
}