/ Vijos / 题库 / 整数分解(版本2) /

题解

179 条题解

  • 0
    @ 2014-07-06 22:13:13

    终于ac
    要把1和2都分析到
    我就这样98

  • 0
    @ 2014-07-06 22:12:27

    program p1033;
    var
    a:array[1..350]of longint;
    c,n,i:longint;
    begin
    readln(n);
    if n=1 then begin writeln(1);halt;end;
    if n=2 then begin writeln(2);halt;end;
    c:=1;
    case n mod 3 of
    0:a[1]:=1;
    1:begin n:=n-4; a[1]:=4; end;
    2:begin n:=n-2; a[1]:=2; end;
    end;
    repeat
    n:=n-3;
    for i:=1 to c do
    a[i]:=a[i]*3;
    for i:=1 to c do
    begin
    a[i+1]:=a[i+1]+a[i]div 10;
    a[i]:=a[i]mod 10;
    end;
    if a[c+1]>0 then inc(c);
    until n=0;
    for i:=c downto 1 do
    write(a[i]);
    end.

  • 0
    @ 2014-02-01 11:25:07

    其实很简单,数学题而已
    对于这道题,记得小学奥赛做过,
    要得到最大值就要**把n尽量拆成3,但是如果拆到最后发现只剩下1的时候应当拿出一个3和剩下的1凑成4**(当然凑成之后可以分成2+2但是不影响结果)
    所以m的值和好确定
    a%3
    0:m=3^(n/3);
    1:m=3^(n/3-1)*4
    2:m=3^(n/3)*2
    剩下的就简单了,只过了几个点?
    谁叫你这么急,要知道n=1500,m=3^500,早就爆了最大的long long了.高精度是肯定的,而且算次方肯定要快速幂呀(虽然不快速幂也能过).
    什么还是没过,那是因为有特俗情况1

    一下是本人代码,代码基本给予麦森数(麦森数是基于高精度乘加了个快速幂)改了一下main的调用和输出函数

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<math.h>
    #define M 10
    #define N 250
    typedef int big[250];
    void base_big(void *a)
    {
    memset(a,0,sizeof(big));
    }
    void smlt(int *r,int b,int *a,int n)
    {
    int static i;
    for (i = 0;i < n-1;i++) {
    *(r+i) += *(a+i)*b;
    *(r+i+1) += *(r+i)/M;
    *(r+i) %= M;
    }
    if (i < n) (r+i) = ((a+i)*b+*(r+i))%M;
    }
    void mlt(int *r,int *b,int a)
    {
    int static j;
    base_big(r);
    for (j = 0;j < N;j++) smlt(r+j,    (b+j),a,N-j);
    }
    void init_big(int *a)
    {
    char s[N+1];
    int i,l;
    scanf("%s",s); l = strlen(s)-1;
    base_big(a);
    for (i = l;i >= 0;i--) *(a+l-i) = s[i]-'0';
    }
    void print(big *a)
    {
    int i;
    for (i = N-1;i > 0;i--) if ((*a)[i]) break; printf("%d",(*a)[i]);
    for (i--;i >= 0;i--) printf("%d",(*a)[i]);
    }
    big tmp;
    void power(int *r,int *a,int n)
    {
    if (n == 0) {
    base_big(r);
    *r = 1;
    return;
    }
    if (n == 1) {
    memcpy(r,a,sizeof(big)); return;
    } else if (n&1) {
    power(r,a,n>>1);
    mlt(tmp,r,r);
    mlt(r,tmp,a);
    } else {
    power(r,a,n>>1);
    mlt(tmp,r,r);
    memcpy(r,tmp,sizeof(big));
    }
    }
    int main()
    {
    big a,c,cc;
    int n;
    base_big(&a); a[0] = 3;
    base_big(&cc);
    scanf("%d",&n);
    if (n <= 3)
    printf("%d",n); else
    switch (n%3) {
    case 1:
    power(c,a,n/3-1);
    cc[0] = 4;
    mlt(a,c,cc);
    print(&a);
    break;
    case 2:
    power(c,a,n/3);
    cc[0] = 2;
    mlt(a,c,cc);
    print(&a);
    break;
    case 0:
    power(c,a,n/3);
    print(&c);
    break;
    }
    return 0;
    }

  • 0
    @ 2013-10-22 23:06:18

    高精+DP
    f[1]=1, f[2]=2, f[3]=3
    f[n]=max{2*f[n-2], 3*f[n-3]} (n>=4)

  • 0
    @ 2013-10-09 21:41:32
    • 没啥，高精度计算 *39数据是1，被坑死了，要特判 ###Block Code #include<iostream> #include<cstdio>

    using namespace std;

    class hugeint
    {
    public:
    int a[1001],n;
    void init()
    {
    n=1;
    a[1]=1;
    }
    void print()
    {
    while(a[n]==0)n--;
    for(int i=n;i>=1;i--){
    cout<<a[i];
    }
    cout<<endl;
    }
    friend hugeint operator*(hugeint a,int b)
    {
    hugeint c;
    int gw=0;
    for(int i=1;i<=a.n;i++){
    c.a[i]=a.a[i]*b+gw;
    gw=c.a[i]/10;
    c.a[i]%=10;
    }
    c.n=a.n;
    while(gw>0){
    c.a[++c.n]=gw%10;
    gw/=10;
    }
    return c;
    }
    };

    int main()
    {

    hugeint a;
    a.init();
    int n;
    cin>>n;
    if(n==1){
    cout<<1<<endl;
    return 0;
    }
    if(n%3==1){
    a=a*4;
    n-=4;
    }
    if(n%3==2){
    a=a*2;
    n-=2;
    }
    for(int i=1;i<=n/3;i++){
    a=a*3;
    }
    // cout<<a.n<<endl;
    a.print();
    return 0;
    }

  • 0
    @ 2013-10-03 15:29:48

    一上来没考虑数据大小啊，跪了一下。然后调整了一下没什么问题了。一个数字最差情况也是1，所以先默认1。往上面乘。输入大于2且不等于4时乘3，然后让输入的数据-3继续循环。如果不符条件了看是不是大于1，大于就乘2，让输入-2。减下来要么剩1要么剩0，都不用考虑。高精那块懒得写函数了，复制黏贴了三遍。

    C++ Code:
    #include <iostream>
    using namespace std;

    int main(){
    int a;
    int result[300];

    for(int i=0;i<=299;i++){
    result[i]=0;
    }

    result[0]=1;
    cin>>a;

    while(a>=3 && a!=4){
    int temp[300];
    for(int i=0;i<=299;i++){
    temp[i]=result[i];
    }
    for(int i=0;i<=299;i++){
    result[i]+=temp[i];
    if(result[i]>=10){
    result[i]-=10;
    result[i+1]+=1;
    }
    }

    for(int i=0;i<=299;i++){
    result[i]+=temp[i];
    if(result[i]>=10){
    result[i]-=10;
    result[i+1]+=1;
    }
    }

    a -=3;
    }

    while(a>1){
    int temp[300];
    for(int i=0;i<=299;i++){
    temp[i]=result[i];
    }
    for(int i=0;i<=299;i++){
    result[i]+=temp[i];
    if(result[i]>=10){
    result[i]-=10;
    result[i+1]+=1;
    }
    }

    a-=2;
    }

    int start=0;
    for(int i=299;i>=0;i--){
    if(result[i]!=0){
    start=i;
    break;
    }

    }
    for (int i=start;i>=0;i--){
    cout<<result[i];
    }

    }

  • 0
    @ 2013-08-07 23:48:24

    当然，高精度的部分最好用函数来解决。鄙人这个地方没有优化，程序可读性有所下降

  • 0
    @ 2013-08-07 23:47:44

    #include<iostream>
    #include<string>
    #include<cstring>

    using namespace std;

    int main(){
    int a[1001] = {0}, w[1001], n;
    cin >> n;
    if (n == 1)
    {
    cout << 1 << endl;
    return 0;
    }
    a[1] = 1;
    memset(w, 0, sizeof(w));
    int rmndr = n % 3, qtnt;
    //cout << "REMINDER = " << rmndr << endl;
    if (rmndr == 0)
    {
    qtnt = n / 3;
    //cout << "QUOTIENT = " << qtnt << endl;
    for (int i = 1; i <= qtnt; i ++)
    {
    memset(w, 0, sizeof(w));
    for (int j = 1; j <= 1000; j ++)
    {
    a[j] = a[j] * 3 + w[j - 1];
    w[j] = a[j] / 10;
    a[j] %= 10;
    }
    }
    int p = 900;
    while (a[p] == 0)p --;
    //cout << "MULTIPLE = ";
    for (int i = p; i >= 1; i --)cout << a[i];
    }
    else if (rmndr == 1)
    {
    qtnt = n / 3;
    //cout << "QUOTIENT = " << qtnt << endl;
    qtnt -= 1;
    for (int i = 1; i <= qtnt; i ++)
    {
    memset(w, 0, sizeof(w));
    for (int j = 1; j <= 1000; j ++)
    {
    a[j] = a[j] * 3 + w[j - 1];
    w[j] = a[j] / 10;
    a[j] %= 10;
    }
    }
    for (int i = 1; i <= 1000; i ++)
    {
    a[i] = a[i] * 4 + w[i - 1];
    w[i] = a[i] / 10;
    a[i] %= 10;
    }
    int p = 900;
    while (a[p] == 0)p --;
    //cout << "MULTIPLE = ";
    for (int i = p; i >= 1; i --)cout << a[i];
    }
    else if (rmndr = 2)
    {
    qtnt = n / 3;
    //cout << "QUOTIENT = " << qtnt << endl;
    for (int i = 1; i <= qtnt; i ++)
    {
    memset(w, 0, sizeof(w));
    for (int j = 1; j <= 1000; j ++)
    {
    a[j] = a[j] * 3 + w[j - 1];
    w[j] = a[j] / 10;
    a[j] %= 10;
    }
    }
    for (int i = 1; i <= 1000; i ++)
    {
    a[i] = a[i] * 2 + w[i - 1];
    w[i] = a[i] / 10;
    a[i] %= 10;
    }
    int p = 900;
    while (a[p] == 0)p --;
    //cout << "MULTIPLE = ";
    for (int i = p; i >= 1; i --)cout << a[i];
    }
    return 0;
    }
    一定要注意n=1的情况！可以看到在程序的最前面我做了一个处理：n=1时输出1直接退出。
    被n=1坑的够惨，第一次49个点中48个正确，WA一个，结果n=1。。。后来AC了

  • 0
    @ 2013-07-17 19:58:26

    #include<stdio.h>
    #include<stdlib.h>
    static int array[3000];
    void jingwei()
    {
    int k;
    int i;
    int j;
    for(i=0;i<3000;i++)
    {
    if(array[i]>9)
    {
    k=array[i]/10;
    array[i]=array[i]%10;
    array[i+1]=array[i+1]+k;
    }
    }
    }
    void chengfa(int n)
    {
    int i;
    for(i=0;i<3000;i++)
    {
    array[i]=array[i]*n;
    }
    }
    int main()
    {
    int n,i,j,k;
    scanf("%d",&n);
    array[0]=1;
    if(n%3==1)
    {
    k=n/3;
    for(i=0;i<k-1;i++)
    {
    chengfa(3);
    jingwei();
    }
    chengfa(4);
    jingwei();
    }
    if(n%3==2)
    {
    k=n/3;
    for(i=0;i<k;i++)
    {
    chengfa(3);
    jingwei();
    }
    chengfa(2);
    jingwei();
    }
    if(n%3==0)
    {
    k=n/3;
    for(i=0;i<k;i++)
    {
    chengfa(3);
    jingwei();
    }
    }
    j=3000;
    int flag=1;
    while(flag)
    {
    j--;
    if(array[j]!=0)flag=0;
    }
    if(n==1)printf("1");
    else for(i=j;i>=0;i--)
    printf("%d",array[i]);
    return 0;
    }
    要考虑1的时候不能直接乘4。。。

  • 0
    @ 2013-04-24 20:43:48

    要细心
    program p1033;
    var m:longint;
    n:string;
    procedure getdata;
    begin
    readln(m);
    end;
    procedure multiply(n:integer;var s:string);
    var a:array[1..500] of integer;
    i,leng:longint;
    begin
    leng:=length(s);
    fillchar(a,sizeof(a),0);
    for i:=1 to length(s) do
    a[length(s)-i+1]:=ord(s[i])-ord('0');
    for i:=1 to length(s) do
    a[i]:=a[i]*n;
    for i:=1 to length(s) do
    if a[i]>=10 then
    begin
    a[i+1]:=a[i+1]+(a[i] div 10);
    a[i]:=a[i] mod 10;
    end;
    s:='';
    if a[leng+1]>0 then
    for i:=leng+1 downto 1 do
    s:=s+chr(a[i]+ord('0'))
    else
    for i:=leng downto 1 do
    s:=s+chr(a[i]+ord('0'));

    end;
    procedure output;
    begin
    writeln(n);
    end;
    function judge(s:longint):longint;
    begin
    if (s=1)or(s=2)or(s=3) then
    judge:=s-1
    else begin
    judge:=(s mod 3)+3;
    end;
    end;
    procedure calc(s:longint;var n:string);
    var i:longint;
    begin
    n:='1';
    case judge(s) of
    0:n:='1';
    1:n:='2';
    2:n:='3';
    3:begin
    for i:=1 to (s div 3) do
    multiply(3,n);
    end;
    4:begin
    for i:=1 to ((s div 3)-1) do
    multiply(3,n);
    for i:=1 to 2 do
    multiply(2,n);
    end;
    5:begin
    for i:=1 to (s div 3) do
    multiply(3,n);
    multiply(2,n);
    end;
    end;
    end;
    begin
    getdata;
    calc(m,n);
    output;
    end.
    测试数据 #0: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #1: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #2: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #3: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #4: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #5: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #6: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #7: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #8: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #9: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #10: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #11: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #12: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #13: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #14: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #15: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #16: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #17: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #18: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #19: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #20: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #21: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #22: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #23: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #24: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #25: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #26: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #27: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #28: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #29: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #30: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #31: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #32: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #33: Accepted, time = 2 ms, mem = 632 KiB, score = 2
    测试数据 #34: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #35: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #36: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #37: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #38: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #39: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #40: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #41: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #42: Accepted, time = 0 ms, mem = 632 KiB, score = 2
    测试数据 #43: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #44: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #45: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #46: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #47: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #48: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    测试数据 #49: Accepted, time = 3 ms, mem = 632 KiB, score = 2
    Accepted, time = 141 ms, mem = 632 KiB, score = 100
    有几位神犇0ms 过的 求指教

    • @ 2014-04-07 20:16:47

      数据不大可以打表啊

  • 0
    @ 2013-02-16 10:14:57

    点击查看程序源码+详细题解

  • 0
    @ 2012-11-05 17:13:19

    Var

    i,j,k,m,n:Longint;

    ans:Int64;

    Begin

    Read(n);

    ans:=1;

    While n-3>1 Do

    Begin

    ans:=ans*3;

    n:=n-3;

    End;

    If n=4 Then Writeln(ans*4);

    If n=3 Then Writeln(ans*3);

    If n=2 Then Writeln(ans*2);

    End.

  • 0
    @ 2012-10-17 09:21:12

    http://user.qzone.qq.com/1304445713/blog/1350436781

    完整证明过程及C++高精度类代码。

    空间不设访问权限，没有烦人的登录动画。

    最近努力写各个OJ的题解，虽然都是些基础向的题目。

    欢迎大家光临~

  • 0
    @ 2009-11-11 16:30:44

    大家都知道，如果这题分解个数可以为实数（比较抽象）且不一定分解成整数的话，那么分出(n/e)个e是最优解

    证明略..有兴趣的同学不妨自己推导一番.

    e=2.718281828..

    显然它比较靠近3,对比可知3越多越好,但是分解个数是整数,所以还要考虑分配平均的问题,这样不难得到下面大牛们的证明.

  • 0
    @ 2009-11-07 16:38:27

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ├ 测试数据 11：答案正确... 0ms

    ├ 测试数据 12：答案正确... 0ms

    ├ 测试数据 13：答案正确... 0ms

    ├ 测试数据 14：答案正确... 0ms

    ├ 测试数据 15：答案正确... 0ms

    ├ 测试数据 16：答案正确... 0ms

    ├ 测试数据 17：答案正确... 0ms

    ├ 测试数据 18：答案正确... 0ms

    ├ 测试数据 19：答案正确... 0ms

    ├ 测试数据 20：答案正确... 0ms

    ├ 测试数据 21：答案正确... 0ms

    ├ 测试数据 22：答案正确... 0ms

    ├ 测试数据 23：答案正确... 0ms

    ├ 测试数据 24：答案正确... 0ms

    ├ 测试数据 25：答案正确... 0ms

    ├ 测试数据 26：答案正确... 0ms

    ├ 测试数据 27：答案正确... 0ms

    ├ 测试数据 28：答案正确... 0ms

    ├ 测试数据 29：答案正确... 0ms

    ├ 测试数据 30：答案正确... 0ms

    ├ 测试数据 31：答案正确... 0ms

    ├ 测试数据 32：答案正确... 0ms

    ├ 测试数据 33：答案正确... 0ms

    ├ 测试数据 34：答案正确... 0ms

    ├ 测试数据 35：答案正确... 0ms

    ├ 测试数据 36：答案正确... 0ms

    ├ 测试数据 37：答案正确... 0ms

    ├ 测试数据 38：答案正确... 0ms

    ├ 测试数据 39：答案正确... 0ms

    ├ 测试数据 40：答案正确... 0ms

    ├ 测试数据 41：答案正确... 0ms

    ├ 测试数据 42：答案正确... 0ms

    ├ 测试数据 43：答案正确... 0ms

    ├ 测试数据 44：答案正确... 0ms

    ├ 测试数据 45：答案正确... 0ms

    ├ 测试数据 46：答案正确... 0ms

    ├ 测试数据 47：答案正确... 0ms

    ├ 测试数据 48：答案正确... 0ms

    ├ 测试数据 49：答案正确... 0ms

    ├ 测试数据 50：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

  • 0
    @ 2009-11-06 22:58:45

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ├ 测试数据 11：答案正确... 0ms

    ├ 测试数据 12：答案正确... 0ms

    ├ 测试数据 13：答案正确... 0ms

    ├ 测试数据 14：答案正确... 0ms

    ├ 测试数据 15：答案正确... 0ms

    ├ 测试数据 16：答案正确... 0ms

    ├ 测试数据 17：答案正确... 0ms

    ├ 测试数据 18：答案正确... 0ms

    ├ 测试数据 19：答案正确... 0ms

    ├ 测试数据 20：答案正确... 0ms

    ├ 测试数据 21：答案正确... 0ms

    ├ 测试数据 22：答案正确... 0ms

    ├ 测试数据 23：答案正确... 0ms

    ├ 测试数据 24：答案正确... 0ms

    ├ 测试数据 25：答案正确... 0ms

    ├ 测试数据 26：答案正确... 0ms

    ├ 测试数据 27：答案正确... 0ms

    ├ 测试数据 28：答案正确... 0ms

    ├ 测试数据 29：答案正确... 0ms

    ├ 测试数据 30：答案正确... 0ms

    ├ 测试数据 31：答案正确... 0ms

    ├ 测试数据 32：答案正确... 0ms

    ├ 测试数据 33：答案正确... 0ms

    ├ 测试数据 34：答案正确... 0ms

    ├ 测试数据 35：答案正确... 0ms

    ├ 测试数据 36：答案正确... 0ms

    ├ 测试数据 37：答案正确... 0ms

    ├ 测试数据 38：答案正确... 0ms

    ├ 测试数据 39：答案正确... 0ms

    ├ 测试数据 40：答案正确... 0ms

    ├ 测试数据 41：答案正确... 0ms

    ├ 测试数据 42：答案正确... 0ms

    ├ 测试数据 43：答案正确... 0ms

    ├ 测试数据 44：答案正确... 0ms

    ├ 测试数据 45：答案正确... 0ms

    ├ 测试数据 46：答案正确... 0ms

    ├ 测试数据 47：答案正确... 0ms

    ├ 测试数据 48：答案正确... 0ms

    ├ 测试数据 49：答案正确... 0ms

    ├ 测试数据 50：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    虽然是因为数据弱

    但还是一个字：爽

  • 0
    @ 2009-11-04 19:13:42

    同一个程序叫了两遍就AC了.........

    那个超时得点怎么解决

    虽然过了但是总觉得很猥琐.......

  • 0
    @ 2009-11-01 13:50:41

    http://hi.baidu.com/lehrlukas/blog/item/6bbb88fc9d8f571c08244d31.html

    除了1要特殊判别一下，其它数据看除以3余几，就有余数个2，其余全是3.然后一个高精度乘法搞定。至于为什么这样最大，这里有人证明过了。粘一下，不介意吧？

    （song19931218的证明）

    经典的数学题：

    若将N分解成以下形式：

    N=x1+x2+...+xk;

    首先证明：

    x(i)

  • 0
    @ 2009-10-31 14:37:13

    一星半纪念题

  • 0
    @ 2009-10-29 16:27:46

    我数学太弱了..参照大牛的方法过了..ToT..!!!

    program vijos1033;

    type bignum=array[0..1000]of integer;

    var n,ans,rem:integer;

    a:bignum;

    function mul(a:bignum;b:integer):bignum;

    var i,x:integer;

    begin

    i:=1; x:=0;

    for i:=1 to a[0] do

    begin

    x:=x+a[i]*b;

    a[i]:=x mod 10;

    x:=x div 10;

    end;

    while x>0 do

    begin

    inc(i);

    a[i]:=x mod 10;

    x:=x div 10;

    end;

    a[0]:=i;

    mul:=a;

    end;

    function fang(a:bignum;b:integer):bignum;

    var i:integer;

    begin

    for i:=1 to b do

    a:=mul(a,3);

    fang:=a;

    end;

    begin

    readln(n); a[0]:=1; a[1]:=1;

    if n=1 then begin write(1); exit; end;

    ans:=n div 3; rem:=n mod 3;

    case rem of

    0:a:=fang(a,ans);

    1:a:=mul(fang(a,ans-1),4);

    2:a:=mul(fang(a,ans),2);

    end;

    for n:=a[0] downto 1 do

    write(a[n]);

    end.

整数分解(版本2)

信息

ID
1033
难度
5
分类
其他 | 数学 点击显示
标签
(无)
递交数
3722
已通过
1204
通过率
32%
被复制
9
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1