如果我能从函数返回多个值,我感兴趣.例如,考虑这样一个函数:扩展欧几里德算法.基本步骤由此输入描述非负整数a和b; 输出是三元组(d,i,j)d=gcd(a,b)=i*a+j*b.为了澄清我的问题的目标,我将编写一个简短的递归代码:
if (b==0) return (a,1,0)
q=a mod b;
让我这样 a=r*b+q;
(d,k,l)=extendedeuclidean(b,q);
return (d,l,k-l*r);
如何归还三胞胎？
我正在尝试使用fmod函数,但我没有得到我期待的结果.
我必须计算超过2到100000的不同素因子的数量,有没有比我正在做的快速方法？即.2有1个不同的素因子2 10有2个不同的素因子(2,5)12有2个不同的素因子(2,3)我的代码: -
#include<stdio.h>
#include<math.h>
typedef unsigned long long ull;
char prime[100000]={0};
int P[10000],fact[100000],k;
void sieve()
{
int i,j;
P[k++]=2;
for(i=3;i*i<1000;i+=2)
{
if(!prime[i])
{
P[k++]=i;
for(j=i*i;j<100000;j+=i+i)
prime[j] = 1;
}
}
for(i=1001;i<100000;i+=2)
if(!prime[i])
P[k++]=i;
}
int calc_fact() {
int root,i,count,j;
fact[1]=fact[2]=fact[3]=1;
for(i=4;i<=100000;i++) {
count=0;
root=i/2+1;
for(j=0;P[j]<=root;j++) {
if(i%P[j]==0)count++;
}
if(count==0) fact[i]=1;
else fact[i]=count;
}
return 0;
}
int main(){
int i;
sieve();
calc_fact();
for(i=1;i<10000;i++) printf("%d ,",fact[i]);
return 0;
}
我必须计算N ^ X MOD 10 ^ 18 + 7,我的范围是1 <= N,X <= 10 ^ 18.通常的大模型算法将无法计算这一点.什么是解决这个问题的正确算法我正在使用C++.当范围是10 ^ 18时,10 ^ 18 + 7的最低mod将是10 ^ 18,如果是这样,那么编译器将必须计算10 ^ 18*10 ^ 18.这将导致溢出.
我正在寻找一种方法来表示值范围:0 - 18446744073709551615使用少于8个字节.
我试着想一些可以做到的方法,但没有任何作用.理论上,例如:使用单个字节表示至少2个字节的位序列.但是,2个字节具有65536个不同的位组合,而单个字节仅给出0-255(256个组合)的值范围.
最好的方法可能是改变位的含义.那没关系,但不能有任何精确损失.
我开始认为它根本不可能,但我希望得到其他人关于这个问题的意见和理论.
有两个规则:#1不能有任何精度损失(即,所有数字0 - 18446744073709551615必须是可表示的).#2从标准64位格式转换永远不会导致需要超过7个字节(56位).
这些规则使这一点特别困难.
我已经读了一本竞争性编程书籍一个月了。这本书是由我国（孟加拉国）的世界决赛入围者之一撰写的。需要注意的是，这本书是用我们的母语（孟加拉语）写的，在世界范围内并不那么流行。由于内容是孟加拉语，我无法在这里引用。这就是为什么我首先感到抱歉。
在那本书的数论章节中，给出了许多测试素性的算法。他展示的最佳方案是 O(nloglogn) 中的“埃拉托斯特尼筛法”。但他写了一行。我正在翻译它。“有一种更有效的方法可以在 O(logn) 中测试素数。你自己想一下。如果你没有完成，只需谷歌一下！！”
我用谷歌搜索了一下，但没有找到满意的东西。
真的有可能在 O(logn) 中测试一个数的素数吗？如果可能的话，那么可以得出的结论是在什么范围内？
假设您有 10e4 个数字。每个数字不超过10e6。如果每个数字可以表示为两个素数的倍数，那么如何有效地检查它？
例子：15可以表示为3*5。6可以表示为2*3。但是8不能用两个素数表示。
如何计算a!/(b1! b2! ... bm!) modulo p，p素数在哪里？a和的阶乘b可能非常大（long long int不够），所以我需要传递到模。
我知道什么是扩展欧几里得算法以及为什么在编程中使用它。这是一种非常有用的算法，用于查找数字的逆模。我知道如何在 C++ 中实现它，这就是我在下面在 C++ 中实现它的方式。
typedef pair<int, int> pii;
#define x first
#define y second
pii extendedEuclidean(int a, int b)
{
if(b==0)
return {a,0};
else {
pii d = extendedEuclidean(b, a%b);
return {d.y, d.x - (d.y*(a/b))};
}
}
现在，如果我想找到一个数字的反模，例如 13，其中 mod 是例如 1000007，那么我只需调用这个函数
pair<int, int> res = extendedEuclidean(13, 1000007);
那么结果是
res.first
我的问题是为什么以及在这个递归中究竟发生了什么？以及为什么它会产生正确的结果。
注意：这里 gcd(a, b) 必须是 1。
为了提高我的 python 技能，我有时会在互联网上进行各种挑战（例如在 hackerrank 上）。谷歌搜索其他东西，我发现了这个问题，以及互联网上的随附解决方案，它引起了我的注意：
随着 LAMBCHOP 末日装置的完成，拉姆达指挥官正在为她在银河舞台上的首次亮相做准备 - 但为了华丽的登场，她需要一个宏伟的楼梯！作为她的私人助理，你的任务是弄清楚如何建造有史以来最好的楼梯。
Lambda 为您提供了可用积木类型的概述以及预算。您可以购买不同数量的不同类型的砖块（例如，3 个粉色小砖块或 5 个蓝色花边砖块）。拉姆达指挥官想知道每块砖块可以建造多少种不同类型的楼梯，这样她就可以选择选项最多的那个。
每种类型的楼梯应包含 2 个或更多台阶。不允许有两个台阶处于相同高度 - 每个台阶必须低于前一个台阶。所有台阶必须至少包含一块砖块。台阶的高度被分类为组成该台阶的砖块的总数。例如，当N = 3时，您只有1种选择如何建造楼梯，第一步的高度为2，第二步的高度为1：（#表示一块砖）
#
##
21
当 N = 4 时，你仍然只有 1 个楼梯选择：
#
#
##
31
但是当 N = 5 时，有两种方法可以用给定的砖块建造楼梯。两个楼梯的高度可以为 (4, 1) 或 (3, 2)，如下所示：
#
#
#
##
41
#
##
##
32
编写一个名为answer(n) 的函数，该函数采用正整数n 并返回可以用n 块砖建造的不同楼梯的数量。n 永远至少为 3（这样你就可以有一个楼梯），但不能超过 200，因为 Lambda 指挥官不是有钱人！
https://en.wikipedia.org/wiki/Partition_(number_theory)
def answer(n):
# make n+1 coefficients
coefficients = [1]+[0]* n
#go through all the …