結果

問題 No.1006 Share an Integer
ユーザー itt828itt828
提出日時 2020-05-17 15:21:18
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,607 ms / 2,000 ms
コード長 9,989 bytes
コンパイル時間 2,680 ms
コンパイル使用メモリ 123,792 KB
実行使用メモリ 69,084 KB
最終ジャッジ日時 2024-09-25 07:37:04
合計ジャッジ時間 16,872 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
27,432 KB
testcase_01 AC 34 ms
27,472 KB
testcase_02 AC 33 ms
25,564 KB
testcase_03 AC 30 ms
25,392 KB
testcase_04 AC 33 ms
27,380 KB
testcase_05 AC 33 ms
27,312 KB
testcase_06 AC 33 ms
27,368 KB
testcase_07 AC 32 ms
25,684 KB
testcase_08 AC 33 ms
25,684 KB
testcase_09 AC 34 ms
25,556 KB
testcase_10 AC 33 ms
25,772 KB
testcase_11 AC 879 ms
60,564 KB
testcase_12 AC 1,580 ms
69,084 KB
testcase_13 AC 1,607 ms
64,548 KB
testcase_14 AC 1,604 ms
66,704 KB
testcase_15 AC 1,389 ms
66,476 KB
testcase_16 AC 672 ms
36,992 KB
testcase_17 AC 945 ms
48,640 KB
testcase_18 AC 1,382 ms
55,552 KB
testcase_19 AC 1,340 ms
54,528 KB
testcase_20 AC 1,475 ms
56,064 KB
testcase_21 AC 1,568 ms
58,624 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using static Math2;
using static io;
using static Utils;

public class CP {
  public void Solve() {
    var X = Cin<int>();
    var F = Enumerable.Range(0, X + 1).ToArray();
    for (int i = 1; i <= X; ++i) {
      for (int j = 1; j * i <= X; ++j) {
        --F[j * i];
      }
    }
    var ans = new List < (int, int) > ();
    for (int i = 1; i <= X - 1; ++i) {
      var A = i;
      var B = X - i;
      ans.Add((A, Abs(F[A] - F[B])));
    }
    ans.Sort((a, b) => a.Item2 - b.Item2);
    var aans = new List<int>();
    foreach (var x in ans) {
      if (x.Item2 == ans[0].Item2)aans.Add(x.Item1);
      else break;
    }
    aans.Sort();
    foreach (var x in aans)Put(x, X - x);
  }
}

public static class NumberTheory {
  public static Dictionary<long, int> PrimeFactorization(long N) {
    var ret = new Dictionary<long, int>();
    for (long i = 2; i * i <= N; ++i) {
      int cnt = 0;
      while (N % i == 0) {
        cnt++;
        N /= i;
      }
      if (cnt != 0)ret[i] = cnt;
    }
    if (N >= 2)ret[N] = 1;
    return ret;
  }
  public static Dictionary<int, int> FactoricalPF(int N) {
    var ret = new Dictionary<int, int>();
    for (int i = 2; i <= N; ++i) {
      int ni = i;
      for (int j = 2; j * j <= ni; ++j) {
        int cnt = 0;
        while (ni % j == 0) {
          ++cnt;
          ni /= j;
        }
        if (cnt == 0)continue;
        if (ret.ContainsKey(j))
          ret[j] += cnt;
        else ret[j] = cnt;
      }
      if (ni >= 2) {
        if (ret.ContainsKey(ni))
          ret[ni] += 1;
        else ret[ni] = 1;
      }
    }
    return ret;
  }
  public static List<long> DivisorEnumrate(long N) {
    var ret = new List<long>();
    for (long i = 1; i * i <= N; ++i) {
      if (N % i == 0) {
        ret.Add(i);
        ret.Add(N / i);
      }
    }
    return ret;
  }
  public static List<int> seive(int n) {
    var ret = new List<int>();
    bool[] isPrime = new bool[n + 1];
    for (int i = 1; i <= n; ++i)isPrime[i] = true;
    isPrime[1] = false;
    for (int i = 1; i <= n; ++i) {
      int j = i;
      if (isPrime[i])ret.Add(i);
      else continue;
      while (j <= n) {
        j += i;
        if (j > n)continue;
        isPrime[j] = false;
      }
    }
    return ret;
  }
  public static bool isPrime(long n) {
    for (int i = 2; i * i <= n; ++i) {
      if (n % i == 0)return false;
    }
    return true;
  }
}
public static class Math2 {
  public const int INF = 1 << 29;
  public const long INFL = 1L << 60;
  public const long MOD = 1000000007;
  public const long MOD2 = 998244353;

  public static long Power(long a, long b, long MOD = 1000000007) //i^N
  {
    long res = 1;
    while (b > 0) {
      if ((b & 1) != 0)res = res * a % MOD;
      a = a * a % MOD;
      b >>= 1;
    }
    return res;
  }
  public static long Power2(long a, long b) //i^N
  {
    long res = 1;
    while (b > 0) {
      if ((b & 1) != 0)res = res * a;
      a = a * a;
      b >>= 1;
    }
    return res;
  }
  public static long GCD(long a, long b) {
    while (b > 0) {
      var r = a % b;
      a = b;
      b = r;
    }
    return a;
  }
  public static long LCM(long a, long b) => (b / GCD(a, b)) * a;
  public static long Comb(long n, long r, int MOD = 1000000007) {
    if (r > n - r)r = n - r;
    long Nume = 1;
    long Deno = 1;

    if (r > n - r)r = n - r;
    for (long i = 1; i <= r; ++i) {
      Deno = (Deno * i) % MOD;
      Nume = Nume * (n - i + 1) % MOD;
    }
    return (Nume * inv(Deno)) % MOD;
  }
  public static long Comb2(long n, long r) {
    long Nume = 1;
    long Deno = 1;

    if (r > n - r)r = n - r;
    for (long i = 1; i <= r; ++i) {
      Deno *= i;
      Nume *= n - i + 1;
    }
    return Nume / Deno;
  }
  public static long inv(long x, int MOD = 1000000007) {
    return Power(x, MOD - 2, MOD);
  }
}
public static class Utils {
  public static void Swap<T>(ref T A, ref T B) {
    T x = A;
    A = B;
    B = x;
  }
  public static int DigitSum(string N) {

    int ret = 0;
    for (int i = 0; i < N.Length; ++i)ret += N[i] - '0';
    return ret;
  }
  public static string ConvertBase(long N, int K) {
    StringBuilder ret = new StringBuilder();
    while (N > 0) {
      var r = N % K;
      N /= K;
      ret.Append(r);
    }
    return new string(ret.ToString().ToCharArray().Reverse().ToArray());
  }
  public static bool NextPermutation<T>(IList<T> lis, Comparison<T> cmp) {
    int n = lis.Count;
    int i = n - 1;
    while (i - 1 >= 0) {
      if (cmp(lis[i - 1], lis[i]) < 0)break;
      --i;
    }
    if (i == 0)return false;
    int j = i;
    while (j + 1 < n) {
      if (cmp(lis[i - 1], lis[j + 1]) > 0)break;
      ++j;
    }
    (lis[i - 1], lis[j]) = (lis[j], lis[i - 1]);
    int k = i;
    int l = n - 1;
    while (k < l) {
      (lis[k], lis[l]) = (lis[l], lis[k]);

      ++k;
      --l;
    }
    return true;
  }
  public static bool NextPermutation<T>(IList<T> lis) => NextPermutation(lis, Comparer<T>.Default.Compare);
}
public class PriorityQueue<T> {
  List<T> _item;
  public int Count { get { return _item.Count; } }
  bool _isascend { get; set; }
  public T Peek { get { return _item[0]; } }
  Comparison<T> Comp;
  public PriorityQueue(bool IsAscend = true, IEnumerable<T> list = null) : this(Comparer<T>.Default.Compare, IsAscend, list) { }
  public PriorityQueue(Comparison<T> cmp, bool IsAscend = true, IEnumerable<T> list = null) {
    _item = new List<T>();
    _isascend = IsAscend;
    this.Comp = cmp;
    if (list != null) {
      _item.AddRange(list);
      Build();
    }
  }

  private int Compare(int i, int j) => (_isascend ? -1 : 1) * Comp(_item[i], _item[j]);
  private void Swap(int i, int j) { var t = _item[i]; _item[i] = _item[j]; _item[j] = t; }
  private int Parent(int i) => (i - 1) >> 1;
  private int Left(int i) => (i << 1) + 1;
  public T Enqueue(T val) {
    int i = _item.Count;
    _item.Add(val);
    while (i > 0) {
      int p = Parent(i);
      if (Compare(i, p) > 0)
        Swap(i, p);
      i = p;
    }
    return val;
  }
  private void Heapify(int index) {
    for (int i = index, j;
      (j = Left(i)) < _item.Count; i = j) {
      if (j != _item.Count - 1 && Compare(j, j + 1) < 0)j++;
      if (Compare(i, j) < 0)
        Swap(i, j);
    }
  }
  public T Dequeue() {
    T val = _item[0];
    _item[0] = _item[_item.Count - 1];
    _item.RemoveAt(_item.Count - 1);
    Heapify(0);
    return val;
  }
  private void Build() {
    for (var i = (_item.Count >> 1) - 1; i >= 0; i--)
      Heapify(i);
  }
  public bool Any() => Count > 0;
}
class Program {
  static void Main(string[] args) {
    var CP = new CP();
    CP.Solve();
  }
}
public static class io {

  public static void Put(string a) => Console.WriteLine(a);
  public static void Put(params object[] i) => Put(string.Join(" ", i));
  public static void Put<T>(IEnumerable<T> a) => Put(string.Join(" ", a));
  public static void PutV<T>(IEnumerable<T> a) { foreach (var z in a)Put(z); }
  public static void YN(bool i) {
    if (i)Put("Yes");
    else Put("No");
  }
  public static string Str => Console.ReadLine();
  public static string[] Strs => Str.Split(" ");
  public static bool IsTypeEqual<T, U>() => typeof(T).Equals(typeof(U));
  public static T ConvertType<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
  public static T Cast<T>(string s) {
    if (IsTypeEqual<T, int>())return ConvertType<T, int>(int.Parse(s));
    else if (IsTypeEqual<T, long>())return ConvertType<T, long>(long.Parse(s));
    else if (IsTypeEqual<T, double>())return ConvertType<T, double>(double.Parse(s));
    else if (IsTypeEqual<T, char>())return ConvertType<T, char>(char.Parse(s));
    else return ConvertType<T, string>(s);
  }
  public static T[] Castarr<T>(string[] s) {

    var ret = new T[s.Length];
    int i = 0;
    if (IsTypeEqual<T, char>()) {
      var list = new List<T>();
      foreach (var t in s) {
        foreach (var u in t) {
          list.Add(ConvertType<T, char>(char.Parse(u.ToString())));
        }
      }
      return list.ToArray();
    }
    foreach (var t in s) {
      if (IsTypeEqual<T, int>())ret[i++] = ConvertType<T, int>(int.Parse(t));
      else if (IsTypeEqual<T, long>())ret[i++] = ConvertType<T, long>(long.Parse(t));
      else if (IsTypeEqual<T, double>())ret[i++] = ConvertType<T, double>(double.Parse(t));
      else ret[i++] = ConvertType<T, string>(t);
    }
    return ret;
  }
  public static T Cin<T>() { var t = Strs; return (Cast<T>(t[0])); }
  public static(T a1, U a2)Cin<T, U>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1])); }
  public static(T a1, U a2, V a3)Cin<T, U, V>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1]), Cast<V>(t[2])); }
  public static(T a1, U a2, V a3, W a4)Cin<T, U, V, W>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1]), Cast<V>(t[2]), Cast<W>(t[3])); }
  public static(T a1, U a2, V a3, W a4, X a5)Cin<T, U, V, W, X>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1]), Cast<V>(t[2]), Cast<W>(t[3]), Cast<X>(t[4])); }
  public static(T a1, U a2, V a3, W a4, X a5, Y a6)Cin<T, U, V, W, X, Y>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1]), Cast<V>(t[2]), Cast<W>(t[3]), Cast<X>(t[4]), Cast<Y>(t[5])); }
  public static(T a1, U a2, V a3, W a4, X a5, Y a6, Z a7)Cin<T, U, V, W, X, Y, Z>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1]), Cast<V>(t[2]), Cast<W>(t[3]), Cast<X>(t[4]), Cast<Y>(t[5]), Cast<Z>(t[6])); }
  public static T[] Cinarr<T>() { var t = Strs; return Castarr<T>(t); }
  public static T[] CinV<T>(int n) {
    var ret = new T[n];
    for (int i = 0; i < n; ++i) {
      ret[i] = Cin<T>();
    }
    return ret;
  }

  public static T Change<T>(this T x, Func<T, T> f) {
    return f(x);
  }
}
0