3057. 素数进制A+B

看什么看自闭了都

input
3
1,0 2,1
4,2,0 1,2,0
1,0 10,6,4,2,1
output
case #0:
1,0,1
case #1:
1,1,1,0
case #2:
1,0,0,0,0,1
answer
case #0:
1,0,1
case #1:
1,1,1,0
case #2:
1,0,0,0,0,1
checker’s comment
wrong answer: line 5 differ - expected: ‘case #2:’, found: ‘case #2:’

???????????????????????????????????????????????????????????????????????

heliangda

from math import sqrt
def isPrime(n):
for i in range(2,int(sqrt(n))+1):
if n % i == 0:
return False
return True
l = [] #质数表
for x in range(2,103):
if isPrime(x):
l.append(x)
times = eval(input())
for j in range(times):
s = input()
a,b = s.split()
a = a.split(“,”)
b = b.split(“,”)
bitsa = len(a)
bitsb = len(b)
a1 = []
b1 = []
c1 = []
for i in range(26):
c1.append(0)

for i in range(25):
    if i < bitsa:
        a1.append(int(a[-i-1]))
    else:
        a1.append(0)
    if i < bitsb:
        b1.append(int(b[-i-1]))
    else:
        b1.append(0)

for i in range(25):  #c1 直接等于 a1 + b1
    c1[i]=a1[i]+b1[i]

over = 0  # 处理进位 c1要26位以防两个25位的数加起来进位
for i in range(26):
    if over == 1:
        c1[i]+=1
        over = 0
    if c1[i]>=l[i]:
        c1[i]-=l[i]
        over = 1
print("case #",j,":",sep = "")   #输出格式化
flag = False
for i in range(1,26):
    if flag == True:
        print(c1[-i],end = ",")
    if c1[-i] > 0 and flag == False:
        print(c1[-i],end = ",")
        flag = True
print(c1[0])
Li Dao

题目可能有点误导,感觉位权并没有用上

include

using namespace std;
typedef vector BIG;

int issu[1000];
vector su;
int T;

BIG input(string aa)
{
BIG ret,tmp;
stringstream ss(aa);
int xx;
ss>>xx;
tmp.push_back(xx);
while(ss.get()==’,’)
{
ss>>xx;
tmp.push_back(xx);
}
for(int i=tmp.size()-1;i>=0;i–) ret.push_back(tmp[i]);
return ret;
}

BIG operator+(const BIG& aa,const BIG& bb)
{
BIG ret;
for(int i=0;i<min(aa.size(),bb.size());i++) ret.push_back(aa[i]+bb[i]);
if(aa.size()<bb.size())
{
for(int i=aa.size();i<bb.size();i++) ret.push_back(bb[i]);
}
else
{
for(int i=bb.size();i=su[ret.size()-1]) { int old=ret.size()-1; ret.push_back(ret[old]/su[old]); ret[old]%=su[old]; } return ret; } void print(const BIG& aa) { int ff=1; for(int i=aa.size()-1;i>=0;i–)
if(ff) {ff=0;cout<<aa[i];}
else cout<<’,’<<aa[i];
cout<<endl;
return;
}
int main()
{
for(int i=2;i<=900;i++) issu[i]=1;
for(int i=2;i<=900;i++)
if(issu[i])
for(int j=i*2;j<=900;j+=i)
issu[j]=0;
for(int i=2;i<=900;i++) if(issu[i]) su.push_back(i);

cin>>T;
for(int step=0;step>s1>>s2;
BIG a1=input(s1),a2=input(s2);
BIG a3=a1+a2;
printf(“case #%d:\n”,step);
print(a3);
}
return 0;
}

就是高精度加法变形一下即可。
再套一个素数筛法。
希望对以后的人有用!

10175102262 LarsPendragon

注意:
1. 每一位是满几进一
2. 读取数字要倒着读
3. 质数表不要写错
附C代码:

#include <stdio.h>
#include <string.h>
int main()
{
    int T, I, weight[25]={2,3,5,7,11, 13,17,19,23,29, 31,37,41,43,47, 53,59,61,67,71, 73,79,83,89,97};//满weight[i]进一
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        int n1[26]={0}, n2[26]={0}, i, j, l1, l2, cnt;
        char s1[100], s2[100];
        scanf("%s %s",s1,s2);
        l1=strlen(s1);
        l2=strlen(s2);
        for(i=l1-1, cnt=0, j=1; i+1; i--)//读第一个数
        {
            if(s1[i]==',') {j=1; cnt++;}
            else
            {
                n1[cnt]+=(s1[i]-'0')*j;
                j*=10;
            }
        }
        for(i=l2-1, cnt=0, j=1; i+1; i--)//读第二个数
        {
            if(s2[i]==',') {j=1; cnt++;}
            else
            {
                n2[cnt]+=(s2[i]-'0')*j;
                j*=10;
            }
        }
        for(i=0; i<25; i++)//模拟运算
        {
            n1[i]+=n2[i];
            if(n1[i]>=weight[i])
            {
                n1[i+1]+=n1[i]/weight[i];
                n1[i]%=weight[i];
            }
        }
        printf("case #%d:\n",I);
        for(i=25; i; i--) if(n1[i]) break;
        for(; i; i--) printf("%d,",n1[i]);
        printf("%d\n",n1[i]);
    }
    return 0;
}
你当前正在回复 博客/题目
存在问题!