在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吧。
[解决办法]
让我想想。。。
因数分解？
不好意思。。。我的程序非常烂的。
- 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)); } }}
[解决办法]
[解决办法]
a^b, (a+1)^b, ..... (a + n - 1)^b
a^(b+1), (a+1)^(b+1), ..... (a + n - 1)^(b+1)
.......
a^(b + m - 1),(a+1)^(b + m - 1), ..... (a + n - 1)^(b + m - 1)
如果有两个数是相同的，那么它们一定不会在同一行，也不会在同一列
如果在同一行比如 i1行j1列 i2行j2列 （从0开始 ）
那么(a + i1)^(b+j1) = (a+i2)^(b+j2)
显然 a+i1 和 a+i2可表示为 p^q1 ,p^q2
而且有 q1*(b+j1)=q2*(b+j2)
在查找的时候，可以只用查如下列
2^a1 - a, 2^(a1+1)-a ,... ,2^(a1+b1)-a ( 2^a1 - a >0 , 2^(a1+b1)-a<=10000)
3^a2 - a, 3^(a2+1)-a ,... ,3^(a2+b2)-a 同上
....
100^a99-a,...100^(a99+b99)-a 。。。
然后比较行数与（ai+bj)的积
[解决办法]
- VB.NET code
Dim m As Int64 = 5 Dim n As Int64 = 5 Dim value As New Hashtable For a As Int64 = 2 To m For b As Int64 = 2 To n Dim c As String = Math.Pow(a, b) Console.Write(a & "^" & b & "=" & c.ToString() & ",") If IsNothing(value.Item(c)) Then value.Add(c, a.ToString() & "^" & b) End If Next Console.WriteLine(" ") Next Console.WriteLine("数量：" & value.Count) Console.ReadLine()
[解决办法]
99347607
- C# code
using System;using System.Diagnostics;using System.Text;using System.Threading;using System.Collections.Generic;using System.Linq;class Program{ private const int N = 10000; private static Dictionary<int, int> funResult; private static HashSet<int> baseNumbers; static void Main(string[] args) { InitFunResult(); InitBaseNumber(); int s = (int)Math.Sqrt((double)N); int sum = 0, k = 0; for (int i = 2; i <= N; i++) { if (baseNumbers.Contains(i)) continue; if (i <= s) k = (int)Math.Log((double)N, (double)i); else k = 1; sum += funResult[k]; } Console.WriteLine(sum); Console.Read(); } private static void InitFunResult() { int maxK = (int)Math.Log((double)N, 2d); funResult = new Dictionary<int, int>(maxK); HashSet<int> set = new HashSet<int>(); int p; for (int i = 1; i <= maxK; i++) { if (i == 1) funResult[i] = 0; else funResult[i] = funResult[i - 1]; for (int j = 2; j <= N; j++) { p = i * j; if (set.Add(i * j)) { funResult[i]++; } } } } private static void InitBaseNumber() { baseNumbers = new HashSet<int>(); int s = (int)Math.Sqrt((double)N); int p; for (int i = 2; i <= s; i++) { for (int j = 2; j <= s; j++) { p = (int)Math.Pow((double)i, (double)j); if (p <= N) baseNumbers.Add(p); else break; } } }}using System;using System.Diagnostics;using System.Text;using System.Threading;using System.Collections.Generic;using System.Linq;class Program{ private const int N = 10000; private static Dictionary<int, int> funResult; private static HashSet<int> baseNumbers; static void Main(string[] args) { InitFunResult(); InitBaseNumber(); int s = (int)Math.Sqrt((double)N); int sum = 0, k = 0; for (int i = 2; i <= N; i++) { if (baseNumbers.Contains(i)) continue; if (i <= s) k = (int)Math.Log((double)N, (double)i); else k = 1; sum += funResult[k]; } Console.WriteLine(sum); Console.Read(); } private static void InitFunResult() { int maxK = (int)Math.Log((double)N, 2d); funResult = new Dictionary<int, int>(maxK); HashSet<int> set = new HashSet<int>(); int p; for (int i = 1; i <= maxK; i++) { if (i == 1) funResult[i] = 0; else funResult[i] = funResult[i - 1]; for (int j = 2; j <= N; j++) { p = i * j; if (set.Add(i * j)) { funResult[i]++; } } } } private static void InitBaseNumber() { baseNumbers = new HashSet<int>(); int s = (int)Math.Sqrt((double)N); int p; for (int i = 2; i <= s; i++) { for (int j = 2; j <= s; j++) { p = (int)Math.Pow((double)i, (double)j); if (p <= N) baseNumbers.Add(p); else break; } } }}
[解决办法]
先假设N为100吧.
4 25 8 9 36这种底数不考虑 他等于2^2 5^5 2^3次方。
以2为底，指数的取值可以为:
(2 3 4 5 6 7 8 9 10 11 12 …… 100） 99个
(4 6 8 10 12 14 16 …… 200） 99 - 49 =50个
（49个是重复出现的比如 4 6 8就是以前出现过的）
(6,9,12,15,18,21,…… 300） 99 - N个重复
(6 12 18 …… 102 108 都是重复的,假设N个 )
因为100里面 2^6 = 64 所以 一共可以出现6此这样的情况
(2*6 3*6 4*6 5*6 …… 100*6) 也是 99-N个
然后3-100都是这样的计算。
[解决办法]
- C# code
static void Main() { int m = 10000, n = 10000; filter3(m, n); Console.ReadKey(); } static void filter3(int m, int n) { List<PowerNum> list = PowerNumList(m); list.Sort((x, y) => { if (x.Base != y.Base) { return x.Base - y.Base; } return y.Index - x.Index; }); int count = 0; list.ForEach((x) => { for (int i = n; i >= 2; i--) { int lowindex= x.Index- 1; while (lowindex > 0 && (x.Index * i) / lowindex <= n) { if ((x.Index * i) % lowindex == 0) { //Console.WriteLine("{0}^{1} ={2}^{3}", Math.Pow(x.Base,x.Index),i ,Math.Pow(x.Base,lowindex),i*x.Index/lowindex); count++; break; } lowindex--; } } }); Console.WriteLine("{0},{1}",count,(m-1)*(n-1)-count); } static List<PowerNum> PowerNumList(int max) { Dictionary<int, PowerNum> list = new Dictionary<int, PowerNum>(); for (int i = 2; i <= Math.Sqrt(max); i++) { int n = i, m = 1; while ((n *= i) <= max) { m++; if (!list.ContainsKey(n)) { list[n] = new PowerNum() { Number = n, Base = i, Index = m }; } } } return list.Values.ToList(); } class PowerNum { public int Number { get; set; } public int Base { get; set; } public int Index { get; set; } }
[解决办法]
- C# code
static void Main() { int m =3 ,n =5,M = 10000, N = 10000; filter3(m,n,M, N); Console.ReadKey(); } static void filter3(int s,int p, int m, int n) { List<PowerNum> list = PowerNumList(s, m); int maxIndex = 0; if(list.Count>0)maxIndex = list.Max((x) => { return x.Index; }); int[] indexCount = new int[maxIndex + 1]; for (int i = n; i >= p; i--) { for (int index = maxIndex ; index >= 2; index--) { int lowindex = index - 1; while (lowindex > 0 && index * i <= n * lowindex) { if ((index * i) % lowindex == 0) { indexCount[index]++; break; } lowindex--; } } } int count = 0; list.ForEach((x) => { count += indexCount[x.Index]; }); Console.WriteLine("{0},{1}",count,(m+1-s)*(n+1-p)-count); } static List<PowerNum> PowerNumList(int min, int max) { Dictionary<int, PowerNum> list = new Dictionary<int, PowerNum>(); int sqrt = (int)Math.Sqrt(max); for (int i = min; i <= sqrt; i++) { int n = i, m = 1; while ((n *= i) <= max) { m++; if (!list.ContainsKey(n)) { list[n] = new PowerNum() { Number = n, Base = i, Index = m }; } } } return list.Values.ToList(); } class PowerNum { public int Number { get; set; } public int Base { get; set; } public int Index { get; set; } }