题解 - Vijos

1

搬运工 (syrth0p1) LV 10 @ 2025-12-24 00:42:19

#include<bits/stdc++.h>
using namespace std;

// 结构体：存储逆序的数字数组、小数位数、有效长度
struct Num {
    int dig[1000];  // 逆序存储数字（dig[0]是个位，dig[1]是十位...）
    int dec_len;    // 小数部分的位数
    int len;        // 数字的有效长度
    // 初始化
    Num() {
        memset(dig, 0, sizeof(dig));
        dec_len = 0;
        len = 0;
    }
};

// 将字符转换为对应数字（0-9:0-9，A-I:10-18，不区分大小写）
int char2num(char c) {
    if (c >= '0' && c <= '9') {
        return c - '0';
    } else if (c >= 'A' && c <= 'I') {
        return c - 'A' + 10;
    } else if (c >= 'a' && c <= 'i') {
        return c - 'a' + 10;
    }
    return -1; // 无效字符（题目保证输入合法，此处备用）
}

// 将数字转换为对应字符
char num2char(int n) {
    if (n >= 0 && n <= 9) {
        return n + '0';
    } else if (n >= 10 && n <= 18) {
        return n - 10 + 'A';
    }
    return '?'; // 无效数字（备用）
}

// 读取输入字符串，转换为Num结构体
void getNum(Num &num, int K) {
    string s;
    cin >> s;
    int dot_pos = -1; // 小数点位置（初始为无小数点）
    int n = s.size();
    
    // 先查找小数点位置
    for (int i = 0; i < n; i++) {
        if (s[i] == '.') {
            dot_pos = i;
            num.dec_len = n - i - 1; // 记录小数位数
            break;
        }
    }
    
    // 逆序存储数字（跳过小数点）
    int idx = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '.') continue;
        num.dig[idx++] = char2num(s[i]);
    }
    num.len = idx; // 有效数字长度（逆序）
}

// 高精度K进制乘法：a * b = res
void mul(Num &a, Num &b, Num &res, int K) {
    // 核心乘法：a.dig[i] * b.dig[j] 累加到 res.dig[i+j]
    for (int i = 0; i < a.len; i++) {
        for (int j = 0; j < b.len; j++) {
            res.dig[i + j] += a.dig[i] * b.dig[j];
            // 处理进位（提前处理，避免溢出）
            if (res.dig[i + j] >= K) {
                res.dig[i + j + 1] += res.dig[i + j] / K;
                res.dig[i + j] %= K;
            }
        }
    }
    
    // 确定结果的有效长度
    res.len = a.len + b.len;
    // 去掉末尾多余的0（逆序存储，末尾对应高位）
    while (res.len > 1 && res.dig[res.len - 1] == 0) {
        res.len--;
    }
    // 记录总小数位数
    res.dec_len = a.dec_len + b.dec_len;
}

// 格式化并输出结果
void outNum(Num &res, int K) {
    string s;
    int total_len = res.len;
    int dec_len = res.dec_len;
    
    // 1. 将逆序数字转换为正序字符（先不考虑小数点）
    for (int i = total_len - 1; i >= 0; i--) {
        s += num2char(res.dig[i]);
    }
    
    // 2. 插入小数点
    if (dec_len > 0) {
        // 小数点位置：总长度（正序） - 小数位数
        int dot_idx = s.size() - dec_len;
        if (dot_idx <= 0) {
            // 小数点在最前面，补前导零
            s = string(abs(dot_idx) + 1, '0') + s;
            dot_idx = 1; // 小数点在第一个零后
        }
        s.insert(dot_idx, ".");
    }
    
    // 3. 去除前导零（小数点前的多余零）
    int pre_zero = 0;
    while (pre_zero < s.size() && s[pre_zero] == '0') {
        pre_zero++;
    }
    // 处理特殊情况：如果前导零后是小数点，保留一个零
    if (pre_zero > 0 && s[pre_zero] == '.') {
        pre_zero--;
    }
    // 如果全是零，保留一个零
    if (pre_zero == s.size()) {
        s = "0";
    } else {
        s = s.substr(pre_zero);
    }
    
    // 4. 去除末尾零（小数点后的多余零）
    if (s.find('.') != string::npos) {
        int suf_zero = s.size() - 1;
        while (suf_zero >= 0 && s[suf_zero] == '0') {
            suf_zero--;
        }
        // 如果末尾是小数点，去掉小数点
        if (s[suf_zero] == '.') {
            suf_zero--;
        }
        s = s.substr(0, suf_zero + 1);
    }
    
    // 5. 输出结果
    cout << s << endl;
}

int main() {
    int K;
    cin >> K;
    Num a, b, res;
    
    getNum(a, K);
    getNum(b, K);
    mul(a, b, res, K);
    outNum(res, K);
    
    return 0;
}

1

郑川岚 LV 10 @ 2008-10-12 21:47:23

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

秒杀。。

庆祝AC60题

。。。。

郑灏轩 @ 2021-12-14 21:00:37

祝贺

0

electrodynamix LV 9 @ 2018-10-04 10:35:33

var

n,p1,p2,dian:integer;

a,b:array[1..10000] of integer;

procedure qq;

var

s1,s2:ansistring;

q1,q2,i:integer;

begin

readln(n);

readln(s1);

readln(s2);
p1:=length(s1);

p2:=length(s2);
q1:=pos('.',s1);

q2:=pos('.',s2);
if q10

then begin

dian:=p1-q1; p1:=p1-1;

delete(s1,q1,1);

end;
if q20

then begin

dian:=dian+p2-q2; p2:=p2-1;

delete(s1,q2,1);

end;
for i:=1 to p1 do

if s1[i] in ['A'..'G']

then a[p1-i+1]:=ord(s1[i])-55

else a[p1-i+1]:=ord(s1[i])-ord('0');
for i:=1 to p2 do

if s2[i] in ['A'..'G']

then b[p2-i+1]:=ord(s2[i])-55

else b[p2-i+1]:=ord(s2[i])-ord('0');

end;

procedure main;

var

s:string;

i,j,qq,aa:integer;

c:array[1..10000] of integer;

begin

fillchar(c,sizeof(c),0);

for i:=1 to p1 do

for j:=1 to p2 do

c:=c+b[j]*a[i];
if c[p1+p2]0

then qq:=p1+p2

else qq:=p1+p2-1;
for i:=1 to qq do

if c[i]>=n

then begin

c:=c+(c[i] div n);

c[i]:=c[i] mod n;

end;
if c[qq+1]0

then qq:=qq+1;
s:='';
for i:=1 to qq do

if c[i]>=10

then s:=s+chr(c[i]+55)

else s:=s+chr(c[i]+ord('0'));
if dian>0

then begin

insert('.',s,dian+1);

qq:=qq+1; aa:=0;
for i:=1 to qq do

if s[i]='0'

then inc(aa)

else break;
if s[aa+1]='.'

then delete(s,1,aa+1)

else delete(s,1,aa);
end;
qq:=length(s);

for i:=qq downto 1 do

if s[i]'0'

then break;

if s[i]='.'

then begin

insert('0',s,1);

i:=i+1;

end;
for j:=i downto 1do

write(s[j]);

writeln;

end;
begin

qq;

main;

end.

0

coLor_fish9 LV 10 @ 2009-10-26 19:16:37

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出 63A3...

　├ 错误行输出 1=41...

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

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：90 有效耗时：0ms

悲剧帝求解释 - -

0

oliverthree LV 10 @ 2009-10-24 23:34:57

都说了是精度计算。。为什么还要删最后的0.。。。

0

我是天才他哥 LV 10 @ 2009-10-21 21:28:39

数组还是开大的好

0

芒果木瓜榴莲 LV 9 @ 2009-09-19 00:13:03

同问楼下

我这几天RP到底怎么了……

编译通过...

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

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

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

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

├ 测试数据 05：答案错误...程序输出比正确答案长

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

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

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

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

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

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

Unaccepted 有效得分：90 有效耗时：0ms

var

s1,s2:ansistring;

l,i,j,k,d1,d2,l1,l2,x,y:longint;

a,b,c:array[1..10000]of longint;

procedure print(i:longint);

begin

if i='0')and(s1[i]='0')and(s2[i]0 do begin c[l]:=x mod k;x:=x div k;inc(l);end;dec(l);

y:=1;while c[y]=0do inc(y);dec(y);

if d1+d2=d1+d2)then

for i:=l downto (d1+d2+1)do print(c[i]);

if (y0 then print(c[i]);

end;

end

else begin

write('0.');

for i:=(d1+d2)downto l+1 do write(0);

for i:=l downto y do if i>0 then print(c[i]);

end;

end.

0

LX11111 LV 10 @ 2009-09-18 12:33:43

哪里错了?

编译通过...

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

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

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

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

├ 测试数据 05：答案错误...程序输出比正确答案长

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

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

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

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

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

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

Unaccepted 有效得分：90 有效耗时：0ms

var

s1,s2:ansistring;

k,x,l1,l2,i,j:longint;

xs:integer;ss:ansistring;

a,b,c:array[1..1200]of integer;

begin

readln(k);

readln(s1);

if pos('.',s1)>0 then begin

xs:=length(s1)-pos('.',s1);

delete(s1,pos('.',s1),1);

end;

readln(s2);

if pos('.',s2)>0 then begin

xs:=xs+length(s2)-pos('.',s2);

delete(s2,pos('.',s2),1);

end;

l1:=length(s1);l2:=length(s2);

for i:=1 to l1 do

begin

a[i]:=ord(s1[l1-i+1])-48;

if a[i]>9 then dec(a[i],7);

end;

for i:=1 to l2 do

begin

b[i]:=ord(s2[l2-i+1])-48;

if b[i]>9 then dec(b[i],7);

end;

for i:=1 to l1 do

begin

x:=0;

for j:=1 to l2 do

begin

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

c:=x mod k;

x:=x div k;

end;

j:=i+l2-1;

while x>0 do

begin

inc(j);

c[j]:=x mod k;

x:=x div k;

end;

end;

j:=1200;

while (c[j]=0)and(j>1) do dec(j);

for i:=j downto xs+1 do

begin

if c[i]>9 then ss:=ss+chr(c[i]+55)

else ss:=ss+chr(c[i]+48);

end;

i:=xs;

while (c[i]=0)and(i>0)do dec(i);

if i=0 then begin

writeln(ss);

halt;

end;

ss:=ss+'.';

for i:=xs downto 1 do

begin

if c[i]>9 then ss:=ss+chr(c[i]+55)

else ss:=ss+chr(c[i]+48);

end;

if ss[1]='.'then ss:='0'+ss;

writeln(ss);

end.

0

sxpeter LV 8 @ 2009-07-20 18:33:45

大家注意：一定要开 ansistring!!!!!

0

notblack LV 10 @ 2009-07-08 00:29:34

注意前导0，后导0，小数点的位置。

可以先输入K=10;

试试 0.1*0.1 2*3 2*0.3 这几种数据。

编译通过...

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

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

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

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

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

├ 测试数据 06：答案错误...　

├ 标准行输出 0.09...

├ 错误行输出 .939...

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

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

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

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

前面的零在没有定位小数点的时候就被我删掉了。。。

0

zgx LV 10 @ 2009-05-01 21:59:37

这个

a,b,c:array[1..2000]of longint;

一定要longint不然第一组过不了。

乘法时在一位上最大可能累计18*18*500这么多，

超出integer范围。

0

yxy LV 10 @ 2009-04-10 18:44:05

小数点后的最后一位如果是0，就不打了。

血的教训啊～！

两遍才AC

0

shuixiang LV 9 @ 2009-04-01 18:11:11

请问大牛，我哪里错了！

program gaojingcheng;

const

c:array['A'..'I']of integer=(10,11,12,13,14,15,16,17,18);

w:array[10..18] of char=('A','B','C','D','E','F','G','H','I');

var

a,b:array[1..100] of longint;

d:array[1..200] of longint;

ch:char;

i,j,n,k,p,q,t,m,l,v,z:longint;

f:boolean;

begin

readln(k);m:=0;

while not eoln do

begin

read(ch);

if ch'.' then

begin

inc(i);

if ch in ['A'..'Z'] then a[i]:=c[ch]

else a[i]:=ord(ch)-48;

end

else m:=i;

end;

if m0 then m:=i-m;

readln;

while not eoln do

begin

read(ch);

if ch'.' then

begin

inc(j);

if ch in ['A'..'Z'] then b[j]:=c[ch]

else b[j]:=ord(ch)-48;

end

else v:=j;

end;

if v0 then begin if m0 then m:=m+(j-v) else m:=j-v; end;

for p:=1 to (i div 2) do

begin

t:=a[p];

a[p]:=a;

a:=t;

end;

for p:=1 to (j div 2) do

begin

t:=b[p];b[p]:=b[j-p+1];b[j-p+1]:=t;

end;

l:=i+j+1;

for p:=1 to i+1 do

for q:=1 to j do

begin

d[p+q-1]:=d[p+q-1]+a[p]*b[q];

d[p+q]:=d[p+q-1] div k +d[p+q];

d[p+q-1]:=d[p+q-1] mod k;

end;

q:=l;

while d[q]=0 do dec(q);

for p:=q downto m+1 do

begin

inc(z);

if d[p]>9 then write(w[d[p]])

else write(d[p]);

end;

f:=false;

for p:=m downto 1 do

if d[p]0 then f:=true;

if f then

begin

if z=0 then write('0.') else write('.');

for p:=m downto 1 do

begin

if d[p]>9 then write(w[d[p]])

else write(d[p]);

end;

end;

end.

0

sdvsdv LV 10 @ 2009-02-14 08:07:01

终于搞定了!细节问题很重要!

1.高精度乘法要细心;

2.前后多余的零要去掉;

3.将高精度乘法的进制改为n进制,即将 mod 10,div 10改为 mod n,div n;

4.小数点的位置要确定,当位数不足时前面要补零;

5.字符串要用ansistring.

0

小猪乐乐 LV 8 @ 2009-01-19 21:34:07

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Flag 　　 Accepted

题号　　P1301

类型(?) 　　其它

通过　　301人

提交　　1101次

通过率　　27%

难度　　1

提交讨论题解

0

cgy4ever LV 10 @ 2009-01-13 13:40:29

这题我都交了3次才过..

哎~

0

sza603 LV 6 @ 2009-01-10 11:10:03

#include

using namespace std;

struct num {

char n[1000];

int p;

};

void getnum(num&n) {

char s[501];

int i,p;

cin>>s;

for(i=0;s[i];i++);

for(n.p=p=0;--i>=0;) if(s[i]=='.') n.p=p; else n.n[p++]=s[i]>r;

getnum(a);

getnum(b);

mul(a,b,r);

out(a);

return 0;

}

交了2次...第一次2个n.p写成了0...第6个点0.09变成.9...

面向对象程序:

#include

using namespace std;

struct num {

char n[1000];

int p;

num() {for(int i=0;i>s;

for(i=0;s[i];i++);

for(j=0;--i>=0;) if(s[i]=='.') p=j; else n[j++]=s[i]>r;

a.get();

b.get();

a.mul(b,r);

a.out();

return 0;

}

0

So飞ar翔 LV 10 @ 2008-11-21 21:55:59

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我晕那。。。。调试的时候改ansistring为string忘记改回来了。。。

小小建议下：最后两头删0时用字符串删方便的多。。。我一开始用的指针，麻烦死我了

0

stevenzjc LV 3 @ 2008-11-10 21:53:16

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

秒杀题

0

fz1993322 LV 8 @ 2008-10-22 19:42:15

大牛我哪错了

var

n,p1,p2,dian:integer;

a,b:array[1..10000] of integer;

procedure qq;

var

s1,s2:ansistring;

q1,q2,i:integer;

begin

readln(n);

readln(s1);

readln(s2);

p1:=length(s1);

p2:=length(s2);

q1:=pos('.',s1);

q2:=pos('.',s2);

if q10

then begin

dian:=p1-q1; p1:=p1-1;

delete(s1,q1,1);

end;

if q20

then begin

dian:=dian+p2-q2; p2:=p2-1;

delete(s1,q2,1);

end;

for i:=1 to p1 do

if s1[i] in ['A'..'G']

then a[p1-i+1]:=ord(s1[i])-55

else a[p1-i+1]:=ord(s1[i])-ord('0');

for i:=1 to p2 do

if s2[i] in ['A'..'G']

then b[p2-i+1]:=ord(s2[i])-55

else b[p2-i+1]:=ord(s2[i])-ord('0');

end;

procedure main;

var

s:string;

i,j,qq,aa:integer;

c:array[1..10000] of integer;

begin

fillchar(c,sizeof(c),0);

for i:=1 to p1 do

for j:=1 to p2 do

c:=c+b[j]*a[i];

if c[p1+p2]0

then qq:=p1+p2

else qq:=p1+p2-1;

for i:=1 to qq do

if c[i]>=n

then begin

c:=c+(c[i] div n);

c[i]:=c[i] mod n;

end;

if c[qq+1]0

then qq:=qq+1;

s:='';

for i:=1 to qq do

if c[i]>=10

then s:=s+chr(c[i]+55)

else s:=s+chr(c[i]+ord('0'));

if dian>0

then begin

insert('.',s,dian+1);

qq:=qq+1; aa:=0;

for i:=1 to qq do

if s[i]='0'

then inc(aa)

else break;

if s[aa+1]='.'

then delete(s,1,aa+1)

else delete(s,1,aa);

end;

qq:=length(s);

for i:=qq downto 1 do

if s[i]'0'

then break;

if s[i]='.'

then begin

insert('0',s,1);

i:=i+1;

end;

for j:=i downto 1do

write(s[j]);

writeln;

end;

begin

qq;

main;

end.

题解

40 条题解

多进制高精度乘法

信息

状态

开发

支持

题解

40 条题解

多进制高精度乘法

信息

状态

开发

支持

还没有账户？

登录