Moduli number system
A number system with moduli is defined by a vector of k moduli, [m1,m2, ···,mk].
The moduli must be pairwise co-prime, which means that, for any pair of moduli, the only common factor is 1.
In such a system each number n is represented by a string "-x1--x2-- ... --xk-" of its residues, one for each modulus. The product m1 ... mk must be greater than the given number n which is to be converted in the moduli number system.
For example, if we use the system [2, 3, 5] the number n = 11 is represented by "-1--2--1-",
the number n = 23 by "-1--2--3-". If we use the system [8, 7, 5, 3] the number n = 187 becomes "-3--5--2--1-".
You will be given a number n (n >= 0) and a system S = [m1,m2, ···,mk] and you will return a string "-x1--x2-- ...--xk-" representing the number n in the system S.
If the moduli are not pairwise co-prime or if the product m1 ... mk is not greater than n, return "Not applicable".
Examples:
fromNb2Str(11 [2,3,5]) -> "-1--2--1-"
fromNb2Str(6, [2, 3, 4]) -> "Not applicable", since 2 and 4 are not coprime
fromNb2Str(7, [2, 3]) -> "Not applicable" since 2 * 3 < 7
fromNb2Str 187 [8,7,5,3] -> "-3--5--2--1-"
fromNb2Str 6 [2, 3, 4] -> "Not applicable", since 2 and 4 are not coprime
fromNb2Str 7 [2, 3] -> "Not applicable", since 2 * 3 < 7public static class Kata
{
public static String fromNb2Str(int n, int[] sys)
{
string str = "Not applicable";
bool flag = CoPrimeArray(sys);
if (flag)
{
IEnumerable<int> list = sys.Select(x => n % x);
int result = sys.Aggregate(, (sum, y) => sum * y);
if (result > n)
{
str = string.Join(string.Empty, list.Select(x => string.Format("-{0}-", x)));
}
}
return str;
} public static bool CoPrimeArray(int[] array)
{
bool coPrime = false;
int max = array.Max();
int sqrt = Convert.ToInt32(Math.Floor(Math.Sqrt(max)));
bool[] tempArray = new bool[max + ];
tempArray = tempArray.Select(x => x = true).ToArray();
int prime = ;//质数，从最小的开始
IEnumerable<int> dividePrime = array.Where(x => x % prime == );//获取能够被质数整除的数字的集合
while (true)
{
if (dividePrime.Count() > )
{
//这里的判断涉及到了Linq的延迟加载,随着prime的改变，每一次的dividePrime是不同的
break;
}
//被除数/除数=商
for (int i = prime; i <= sqrt; i++)
{
for (int j = i; j * i < max; j++)
{
//j*i这个位置的数据可以被i整除
if (tempArray[j * i])
{
tempArray[j * i] = false;
}
}
}
while (true)
{
prime++;
if (prime == max)
{
//除数已经达到最大值，说明数组里面的所有数字互质
coPrime = true;
break;
}
else
{
if (tempArray[prime])
{
//说明没有被前面prime个数字整除过,
//假如prime是3的话,并且符合的话，说明3没有被2整除过
//假如prime是7的话，并且符合的话，说明7没有被2到6的数字整除过
break;
}
}
}
if (coPrime)
{
break;
}
}
return coPrime;
}
}
最新文章
- heap c++ 操作 大顶堆、小顶堆
- NBUT 1535
- NSString学习
- QT 的下载地址
- Python开发【第二篇】：初识Python
- 【C#】IDispose接口的应用
- DevExpress汉化(WinForm)
- 关于Python中的self
- Qt读写二进制文件
- OCR怎么能离开扫描仪呢？
- 2017华为机试题--Floyd算法
- 新篇章之我的java学习之路上
- 为hadoop集群设置静态IP
- Dynamics 365 POA表记录的产生
- Spring Security（三十二）：10. Core Services
- kubernetes + istio进行流量管理
- 使用android访问SQLServer数据库
- HTML5 CSS JavaScript在网页中扮演的角色
- EF CodeFirst 初识
- lnmp环境的使用教程