結果
問題 | No.2526 Kth Not-divisible Number |
ユーザー |
![]() |
提出日時 | 2023-11-03 21:42:18 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 436 ms / 2,000 ms |
コード長 | 10,056 bytes |
コンパイル時間 | 9,275 ms |
コンパイル使用メモリ | 167,308 KB |
実行使用メモリ | 210,328 KB |
最終ジャッジ日時 | 2024-09-25 19:46:05 |
合計ジャッジ時間 | 13,713 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 11 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (92 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(64,28): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(65,26): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;using System.Linq;using System.Collections;using System.IO;using System.Collections.Generic;using System.Text;using System.Numerics;using System.Runtime.Intrinsics.X86;using System.Buffers;using System.Diagnostics;using System.Runtime.CompilerServices;using static InputUtility;class Program{static void Main(){using Output output = new(false);InputNewLine();var t = NextInt32;for (int i = 0; i < t; i++){Solve();}}private static void Solve(){InputNewLine();var (a, b, k) = ((ulong)NextInt64, (ulong)NextInt64, (ulong)NextInt64);var lcm = Lcm(a, b);ulong ok = ulong.MaxValue >> 2;var ng = 0UL;while (ok - ng > 1){var mid = (ok + ng) / 2;if (mid - DivisibleCount(mid) >= k){ok = mid;}else{ng = mid;}}ulong DivisibleCount(ulong k) => k / a + k / b - k / lcm;Console.WriteLine(ok);}public static ulong Gcd(ulong a, ulong b) => b == 0 ? a : Gcd(b, a % b);public static ulong Lcm(ulong a, ulong b) => a / Gcd(a, b) * b;}public static class InputUtility{private static string[]? s_inputs;private static string? s_raw;private static int s_index = 0;private static void Init() => s_index = 0;public static int NextInt32 => int.Parse(s_inputs![s_index++]!);public static uint NextUInt32 => uint.Parse(s_inputs![s_index++]!);public static long NextInt64 => long.Parse(s_inputs![s_index++]!);public static BigInteger NextBigInteger => long.Parse(s_inputs![s_index++]!);public static string NextString => s_inputs![s_index++];public static char NextChar => s_inputs![s_index++][0];public static int[] GetInt32Array() => s_inputs!.Select(int.Parse).ToArray();public static long[] GetInt64Array() => s_inputs!.Select(long.Parse).ToArray();public static string GetRawString() => s_raw!;#if DEBUGprivate static TextReader? s_textReader;public static void SetSource(string path) => s_textReader = new StringReader(File.ReadAllText(path));#endifpublic static bool InputNewLine(){#if DEBUGif (s_textReader is TextReader sr){Init();s_raw = sr.ReadLine()!;s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);return true;}#endifInit();s_raw = Console.ReadLine()!;s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);return true;}}public readonly struct Output : IDisposable{private readonly StreamWriter _sw;#if DEBUGpublic Output(string path){var fs = new FileStream(path, FileMode.Create, FileAccess.Write);_sw = new StreamWriter(fs);Console.SetOut(_sw);}#endifpublic Output(bool autoFlush){_sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = autoFlush };Console.SetOut(_sw);}public void Dispose(){_sw.Dispose();}[MethodImpl(MethodImplOptions.AggressiveInlining)]internal void Flush(){_sw.Flush();}}public static class ArrayExtensions{public static void Swap<T>(this T[] array, int i, int j) => (array[i], array[j]) = (array[j], array[i]);public static int LowerBound<T>(this T[] a, T target) where T : IComparable<T>{int ok = a.Length;int ng = -1;while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid)(ok, ng) = a[mid].CompareTo(target) >= 0 ? (mid, ng) : (ok, mid);return ok;}public static int UpperBound<T>(this T[] a, T target) where T : IComparable<T>{int ok = a.Length;int ng = -1;while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid)(ok, ng) = a[mid].CompareTo(target) > 0 ? (mid, ng) : (ok, mid);return ok;}public struct IndexedEnumerable<T> : IEnumerable<(T item, int index)>{private readonly T[] _a;private readonly int _startIndex;public IndexedEnumerable(T[] a, int startIndex = 0){_a = a;_startIndex = startIndex;}public readonly IndexedEnumerator<T> GetEnumerator() => new IndexedEnumerator<T>(_a, _startIndex);IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();IEnumerator<(T item, int index)> IEnumerable<(T item, int index)>.GetEnumerator() => GetEnumerator();}public struct IndexedEnumerator<T> : IEnumerator<(T item, int index)>{public readonly (T item, int index) Current => (_a[_index], _index + _startIndex);private int _index;private int _startIndex;private T[] _a;public IndexedEnumerator(T[] a, int startIndex){_index = -1;_a = a;_startIndex = startIndex;}public bool MoveNext() => ++_index < _a.Length;readonly object IEnumerator.Current => Current;public readonly void Dispose() { }public void Reset() => _index = -1;}/// <returns>(T value, int index)</returns>public static IndexedEnumerable<T> Enumerate<T>(this T[] arr, int startIndex = 0) => new IndexedEnumerable<T>(arr, startIndex);}public static class IEnumerableExtensions{public static IEnumerable<TSource> Log<TSource>(this IEnumerable<TSource> source){Console.WriteLine(string.Join(' ', source));return source;}public static ScanEnumerable<TSource, TAccumulate> Scan<TSource, TAccumulate>(this IEnumerable<TSource> source,TAccumulate seed,Func<TAccumulate, TSource, TAccumulate> accumulator) where TSource : struct where TAccumulate : struct{return new ScanEnumerable<TSource, TAccumulate>(source, accumulator, seed);}public static IEnumerable<TAccumulate> ScanExSeed<TSource, TAccumulate>(this IEnumerable<TSource> source,TAccumulate seed,Func<TAccumulate, TSource, TAccumulate> accumulator){var accumulation = new List<TAccumulate>();var current = seed;foreach (var item in source){current = accumulator(current, item);accumulation.Add(current);}return accumulation;}public readonly struct ScanEnumerable<TSource, TAccumulate> : IEnumerable<TAccumulate> where TSource : struct where TAccumulate : struct{private readonly IEnumerable<TSource> _source;private readonly Func<TAccumulate, TSource, TAccumulate> _accumulator;private readonly TAccumulate _seed;public ScanEnumerable(IEnumerable<TSource> source, Func<TAccumulate, TSource, TAccumulate> accumulator, TAccumulate seed){_source = source;_accumulator = accumulator;_seed = seed;}public readonly ScanEnumerator<TSource, TAccumulate> GetEnumerator() => new(_source, _accumulator, _seed);readonly IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();readonly IEnumerator<TAccumulate> IEnumerable<TAccumulate>.GetEnumerator() => GetEnumerator();}public struct ScanEnumerator<TSource, TAccumulate> : IEnumerator<TAccumulate> where TSource : struct where TAccumulate : struct{private readonly Func<TAccumulate, TSource, TAccumulate> _accumulator;private readonly IEnumerator<TSource> _enumerator;private TAccumulate _current;private bool _secondOrLaterElement = false;public ScanEnumerator(IEnumerable<TSource> source, Func<TAccumulate, TSource, TAccumulate> accumulator, TAccumulate seed){_enumerator = source.GetEnumerator();_accumulator = accumulator;_current = seed;}public readonly TAccumulate Current => _current;readonly object IEnumerator.Current => Current;public readonly void Dispose() { }public bool MoveNext(){if (_secondOrLaterElement){if (_enumerator.MoveNext()){_current = _accumulator(_current, _enumerator.Current);return true;}return false;}else{_secondOrLaterElement = true;return true;}}public void Reset(){throw new NotSupportedException();}}public static IEnumerable<TSource> Scan<TSource>(this IEnumerable<TSource> source,Func<TSource, TSource, TSource> accumulator){if (source is null)throw new ArgumentNullException(paramName: nameof(source));if (accumulator is null)throw new ArgumentNullException(paramName: nameof(accumulator));var accumulation = new List<TSource>();if (source.Any() is false){return accumulation;}var current = source.First();accumulation.Add(current);foreach (var item in source.Skip(1)){current = accumulator(current, item);accumulation.Add(current);}return accumulation;}}public class MyMath{public static long Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(1L, (acc, x) => acc * x);public static long Pow10(int y) => Pow(10, y);public static long Pow2(int y) => Pow(2, y);}public class MyMathBigInteger{public static BigInteger Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(new BigInteger(1), (acc, x) => acc * x);public static BigInteger Pow10(int y) => Pow(10, y);public static BigInteger Pow2(int y) => Pow(2, y);}