在Java区看到一个比较有意思的题目,转过来大家讨论一下,该如何处理
在Java区看到一个比较有意思的题目,转过来大家讨论一下
Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
2^2=4, 2^3=8, 2^4=16, 2^5=32
3^2=9, 3^3=27, 3^4=81, 3^5=243
4^2=16, 4^3=64, 4^4=256, 4^5=1024
5^2=25, 5^3=125, 5^4=625, 5^5=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
翻译一下
就是有一个m*n的矩阵,
该矩阵的第一列是a^b,(a+1)^b,.....(a + n - 1)^b
第二列是a^(b+1),(a+1)^(b+1),.....(a + n - 1)^(b+1)
.......
第m列是(b + m - 1),(a+1)^(b + m - 1),.....(a + n - 1)^(b + m - 1)
问这个矩阵里有多少不重复的数
(比如4^3 = 8^2,这样的话就有重复了)
原题里面m和n的范围为100,这样的话就不用优化了,为了把问题搞难一些,让m和n都为10000吧。
------解决方案--------------------
让我想想。。。
因数分解?
不好意思。。。我的程序非常烂的。
Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
2^2=4, 2^3=8, 2^4=16, 2^5=32
3^2=9, 3^3=27, 3^4=81, 3^5=243
4^2=16, 4^3=64, 4^4=256, 4^5=1024
5^2=25, 5^3=125, 5^4=625, 5^5=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
翻译一下
就是有一个m*n的矩阵,
该矩阵的第一列是a^b,(a+1)^b,.....(a + n - 1)^b
第二列是a^(b+1),(a+1)^(b+1),.....(a + n - 1)^(b+1)
.......
第m列是(b + m - 1),(a+1)^(b + m - 1),.....(a + n - 1)^(b + m - 1)
问这个矩阵里有多少不重复的数
(比如4^3 = 8^2,这样的话就有重复了)
原题里面m和n的范围为100,这样的话就不用优化了,为了把问题搞难一些,让m和n都为10000吧。
------解决方案--------------------
让我想想。。。
因数分解?
不好意思。。。我的程序非常烂的。
- C# code
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { class Node { public int Num { get; set; } public Dictionary<int, int> Count { get; set; } public Node() { Count = new Dictionary<int, int>(); } public override string ToString() { string s = ""; foreach (var i in Count) { s += "|" + Math.Pow((double)Num, (double)i.Key).ToString() + " " + i.Value.ToString(); } return s; } } static Dictionary<int, Node> Nodes = new Dictionary<int, Node>(); static List<int> Primers = new List<int>() { }; static void ProcPrimes(int num) { bool noprime = false; foreach (var i in Primers) { if (num % i == 0) { noprime = true; break; } else { if (i > num) break; } } if (!noprime) Primers.Add(num); } static void ToNodes(int num, int power) { List<int> list = new List<int>(); foreach (var i in Primers) { if (num % i == 0) { list.Add(i); break; } else { if (i > num) break; } } int x = 1; list.ForEach(x1 => x *= x1); if (!Nodes.ContainsKey(x)) Nodes.Add(x, new Node(){ Num = x }); int pwr = num / x * power; if (!Nodes[x].Count.ContainsKey(pwr)) Nodes[x].Count.Add(pwr, 1); else Nodes[x].Count[pwr]++; } static int Solve(int startA, int endA, int startB, int endB) { Debug.Assert(startA > 1 && startB > 1); Debug.Assert(endA > startA && endB > startB); for (int i = 2; i <= endA; i++) ProcPrimes(i); for (int i = startA; i <= endA; i++) for (int j = startB; j <= endB; j++) ToNodes(i, j); Nodes.Values.ToList() .ForEach(x => (from y in x.Count where y.Value > 0 select Math.Pow((double)x.Num, (double)y.Key)) .ToList().ForEach(z => Debug.WriteLine(z))); int n = 0; Nodes.ToList().ForEach(x => n += x.Value.Count.Count); return n; } static void Main(string[] args) { Console.WriteLine(Solve(2, 1000, 2, 1000)); } } }