using System; using System.Linq; using CompLib.Util; using System.Threading; using CompLib.DataStructure; using CompLib.Mathematics; public class Program { private int L, R; public void Solve() { var sc = new Scanner(); L = sc.NextInt(); R = sc.NextInt(); int e = 0; var uf = new UnionFind(R + 1); long ans = 0; for (int m = 0; e < R - L; m++) { for (int i = L; i <= R && e < R - L; i++) { for (int j = i + m; j <= R && e < R - L; j += i) { if (uf.Connect(i, j)) { e++; ans += m; } } } } Console.WriteLine(ans); } public static void Main(string[] args) => new Program().Solve(); // public static void Main(string[] args) => new Thread(new Program().Solve, 1 << 27).Start(); } namespace CompLib.DataStructure { using System.Collections.Generic; using System.Linq; class UnionFind { private readonly int _n; private readonly int[] _parent, _size; /// /// n頂点の無向グラフに 1.辺を追加, 2.2頂点が同じ連結成分に属するか判定 ができるデータ構造 /// /// 頂点の個数 public UnionFind(int n) { _n = n; _parent = new int[_n]; _size = new int[_n]; for (int i = 0; i < _n; i++) { _parent[i] = i; _size[i] = 1; } } /// /// iがいる連結成分の代表値 /// /// /// public int Find(int i) => _parent[i] == i ? i : Find(_parent[i]); /// /// x,yが同じ連結成分にいるか? /// /// /// /// public bool Same(int x, int y) => Find(x) == Find(y); /// /// (x, y)に辺を追加する /// /// /// ACLでは連結された代表値を返しますが、ここでは連結できたか?を返します /// /// /// /// x,yが違う連結成分だったならtrueを返す public bool Connect(int x, int y) { x = Find(x); y = Find(y); if (x == y) return false; // データ構造をマージする一般的なテク if (_size[x] > _size[y]) { _parent[y] = x; _size[x] += _size[y]; } else { _parent[x] = y; _size[y] += _size[x]; } return true; } /// /// iが含まれる成分のサイズ /// /// /// public int GetSize(int i) => _size[Find(i)]; /// /// 連結成分のリスト /// /// public List[] Groups() { var leaderBuf = new int[_n]; var groupSize = new int[_n]; for (int i = 0; i < _n; i++) { leaderBuf[i] = Find(i); groupSize[leaderBuf[i]]++; } var result = new List[_n]; for (int i = 0; i < _n; i++) { result[i] = new List(groupSize[i]); } for (int i = 0; i < _n; i++) { result[leaderBuf[i]].Add(i); } return result.Where(ls => ls.Count > 0).ToArray(); } } } // https://bitbucket.org/camypaper/complib namespace CompLib.Mathematics { using System; using System.Collections.Generic; #region GCD LCM /// /// 様々な数学的関数の静的メソッドを提供します. /// public static partial class MathEx { /// /// 2 つの整数の最大公約数を求めます. /// /// 最初の値 /// 2 番目の値 /// 2 つの整数の最大公約数 /// ユークリッドの互除法に基づき最悪計算量 O(log N) で実行されます. public static int GCD(int n, int m) { return (int) GCD((long) n, m); } /// /// 2 つの整数の最大公約数を求めます. /// /// 最初の値 /// 2 番目の値 /// 2 つの整数の最大公約数 /// ユークリッドの互除法に基づき最悪計算量 O(log N) で実行されます. public static long GCD(long n, long m) { n = Math.Abs(n); m = Math.Abs(m); while (n != 0) { m %= n; if (m == 0) return n; n %= m; } return m; } /// /// 2 つの整数の最小公倍数を求めます. /// /// 最初の値 /// 2 番目の値 /// 2 つの整数の最小公倍数 /// 最悪計算量 O(log N) で実行されます. public static long LCM(long n, long m) { return (n / GCD(n, m)) * m; } } #endregion #region PrimeSieve public static partial class MathEx { /// /// ある値までに素数表を構築します. /// /// 最大の値 /// 素数のみを入れた数列が返される /// 0 から max までの素数表 /// エラトステネスの篩に基づき,最悪計算量 O(N loglog N) で実行されます. public static bool[] Sieve(int max, List primes = null) { var isPrime = new bool[max + 1]; for (int i = 2; i < isPrime.Length; i++) isPrime[i] = true; for (int i = 2; i * i <= max; i++) if (!isPrime[i]) continue; else for (int j = i * i; j <= max; j += i) isPrime[j] = false; if (primes != null) for (int i = 0; i <= max; i++) if (isPrime[i]) primes.Add(i); return isPrime; } } #endregion } namespace CompLib.Util { using System; using System.Linq; class Scanner { private string[] _line; private int _index; private const char Separator = ' '; public Scanner() { _line = new string[0]; _index = 0; } public string Next() { if (_index >= _line.Length) { string s; do { s = Console.ReadLine(); } while (s.Length == 0); _line = s.Split(Separator); _index = 0; } return _line[_index++]; } public string ReadLine() { _index = _line.Length; return Console.ReadLine(); } public int NextInt() => int.Parse(Next()); public long NextLong() => long.Parse(Next()); public double NextDouble() => double.Parse(Next()); public decimal NextDecimal() => decimal.Parse(Next()); public char NextChar() => Next()[0]; public char[] NextCharArray() => Next().ToCharArray(); public string[] Array() { string s = Console.ReadLine(); _line = s.Length == 0 ? new string[0] : s.Split(Separator); _index = _line.Length; return _line; } public int[] IntArray() => Array().Select(int.Parse).ToArray(); public long[] LongArray() => Array().Select(long.Parse).ToArray(); public double[] DoubleArray() => Array().Select(double.Parse).ToArray(); public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray(); } }