Advertisement
Guest User

Untitled

a guest
Sep 21st, 2014
515
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.85 KB | None | 0 0
  1. import java.awt.*;
  2. import java.io.*;
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.StringTokenizer;
  6.  
  7. public class C {
  8.  
  9.     BufferedReader in;
  10.     PrintWriter out;
  11.     StringTokenizer tok = new StringTokenizer("");
  12.  
  13.     public static void main(String[] args) {
  14.         new C().run();
  15.     }
  16.  
  17.     public void run() {
  18.         try {
  19.             long t1 = System.currentTimeMillis();
  20.  
  21.             init();
  22.             solve();
  23.  
  24.             out.close();
  25.  
  26.             long t2 = System.currentTimeMillis();
  27.             System.err.println(t2 - t1);
  28.         } catch (Exception e) {
  29.             e.printStackTrace();
  30.             System.exit(-1);
  31.         }
  32.     }
  33.  
  34.     void init() throws  IOException {
  35.         try {
  36.             in = new BufferedReader(new FileReader("input.txt"));
  37.             out = new PrintWriter("output.txt");
  38.         } catch (Exception e) {
  39.             in = new BufferedReader(new InputStreamReader(System.in));
  40.             out = new PrintWriter(System.out);
  41.         }
  42.     }
  43.  
  44.     String readString() throws IOException {
  45.         while (!tok.hasMoreTokens()) {
  46.             try {
  47.                 tok = new StringTokenizer(in.readLine());
  48.             } catch (Exception e) {
  49.                 return null;
  50.             }
  51.         }
  52.  
  53.         return tok.nextToken();
  54.     }
  55.  
  56.     int readInt() throws  IOException {
  57.         return Integer.parseInt(readString());
  58.     }
  59.  
  60.     long readLong() throws  IOException {
  61.         return Long.parseLong(readString());
  62.     }
  63.  
  64.     void solve() throws  IOException {
  65.         int k = readInt();
  66.  
  67.         List<Integer> divisors = new ArrayList<Integer>();
  68.         for (int d = 1; d * d <= k; ++d) {
  69.             if (k % d == 0) {
  70.                 divisors.add(d);
  71.                 if (d * d != k) {
  72.                     divisors.add(k / d);
  73.                 }
  74.             }
  75.         }
  76.  
  77.         class Pair {
  78.             long a, b;
  79.  
  80.             public Pair(long a, long b) {
  81.                 this.a = a;
  82.                 this.b = b;
  83.             }
  84.         }
  85.         List<Pair> answers = new ArrayList<Pair>();
  86.  
  87.         int size = divisors.size();
  88.         for (int a: divisors) {
  89.             for (int i = 0; i < size; ++i) {
  90.                 int b = divisors.get(i);
  91.                 int gcd = gcd(a, b);
  92.  
  93.                 if (gcd == 1) {
  94.                     long sum = a + b;
  95.                     sum *= k;
  96.  
  97.                     long mult = 1L * a * b;
  98.                     if (sum % mult != 0) continue;
  99.  
  100.                     long g = sum / mult;
  101.                     answers.add(new Pair(g * a, g * b));
  102.                  }
  103.             }
  104.         }
  105.  
  106.         out.println(answers.size());
  107.         for (Pair answer: answers) {
  108.             out.println(answer.a + " " + answer.b);
  109.         }
  110.     }
  111.  
  112.     int gcd(int a, int b) {
  113.         return (a == 0? b: gcd(b % a, a));
  114.     }
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement