Submission #335526

#	Time	Username	Problem	Language	Result	Execution time	Memory
335526		KWang31	Nice sequence (IZhO18_sequence)	Java	100 / 100	917 ms	62040 KiB

sequence

import java.io.*; import java.util.*;
public class sequence{
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        
    } 
    public static class Pair implements Comparable<Pair>{
        int vtx; int val;
        public Pair(int a, int b){
            this.vtx=a; this.val=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.vtx<other.vtx)return -1;
            return 1;
        }
    }
    static int MOD=1000000;
    
    public static void main(String[] args){
        
        FastReader br=new FastReader();
        int T=br.nextInt();
        while(T>0){
            T--;
            int N=br.nextInt(); int M=br.nextInt();
            
            int d=gcd(N,M); int n=N/d; int m=M/d;
            
            if((long) n*m==1){
                
                System.out.println(M-1);
                StringBuilder sb=new StringBuilder();
                for (int i = 1; i < M; i++) {
                    sb.append(1+" ");
                }
                System.out.println(sb.toString()); continue;
            }
            int[] psa=new int[n+m-1]; //psa[0]=0
            int cur=n-1;
            for (int i = 0; i < n+m-2; i++) {
                
                if(cur>=m){
                    psa[cur-m]=psa[cur]-1; cur-=m;
                }else{
                    psa[cur+n]=psa[cur]-1; cur+=n;
                }
            }
            for (int i = n+m-2; i >=0; i--) {
                psa[i]-=psa[0];
            }
            long[] ans=new long[N+M-d];
            
            boolean[] pos=new boolean[n+m-1];
            boolean[] neg=new boolean[n+m-1];
            for (int i = 1; i < n+m-1; i++) {
                if(psa[i]-psa[i-1]>0){
                    pos[psa[i]-psa[i-1]]=true;
                }else{
                    neg[psa[i-1]-psa[i]]=true;
                }
            }
            
            if(d==1){
                for (int j = 0; j < n+m-1; j++) {
                    for (int i = 0; i < d; i++) {
                        ans[j*d+i]=(long) MOD*i+psa[j];
                    
                    }
                }
            }else{
                int c=1; while((d-1)*c<n+m-1 && pos[(d-1)*c])c++;
                int z=1; while((d-1)*z<n+m-1 && neg[(d-1)*z])z++;
                c=Math.min(c,-z);
                for (int j = 0; j < n+m-1; j++) {
                    for (int i = 0; i < d; i++) {
                        ans[j*d+i]=(long) c*i+psa[j];
                    
                    }
                }
            }
            
            System.out.println(N+M-d-1);
            
            if(N+M-d>1){
                StringBuilder sb=new StringBuilder();
                for (int i = 1; i < N+M-d; i++) {
                    sb.append((long) (ans[i]-ans[i-1])+" ");
                }
                System.out.println(sb.toString());
            }
        }
        
        
    }
    public static int gcd(int a, int b){//Assumes a>b
        if(b==0)return a;
        return gcd(b,a%b);
    }
    
    
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24