Submission #335522

#	Time	Username	Problem	Language	Result	Execution time	Memory
335522		KWang31	Nice sequence (IZhO18_sequence)	Java	15 / 100	873 ms	21940 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;
            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];
            for (int i = 0; i < d; i++) {
                for (int j = 0; j < n+m-1; j++) {
                    ans[j*d+i]=(long) d*i+psa[j];
                }
            }
            //System.out.println(Arrays.toString(ans));
            System.out.println(N+M-d-1);
            
            for (int i = 1; i < N+M-d; i++) {
                System.out.print((long) ans[i]-ans[i-1]+" ");
            }
            if(N+M-d>1)System.out.println("");
        }
        
        
    }
    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: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24