/ Vijos / 题库 / 循环 /

# 104 条题解

• @ 2017-08-07 21:27:53

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
struct hp

{
int s[210];
} n,a,b,ans;
char N[110];
int k,now,tmp;

void mult1(hp a,hp b,hp &c,int d)
{
hp s;
memset(s.s,0,sizeof(s.s));
for(int i=1;i<=d;i++)
for(int j=1;j<=d;j++)
s.s[i+j-1]+=a.s[i]*b.s[j];
for(int i=1;i<=d+1;i++)
if (s.s[i]>=10)
{
s.s[i+1]+=s.s[i]/10;
s.s[i]%=10;
}
c=s;
}

void mult2(hp a,int b,hp &c)
{
hp s;
memset(s.s,0,sizeof(s.s));
for(int i=1;i<=200;i++)
s.s[i]+=a.s[i]*b;
for(int i=1;i<=200;i++)
if (s.s[i]>=10)
{
s.s[i+1]+=s.s[i]/10;
s.s[i]%=10;
}
c=s;
}

int main()
{
scanf("%s %d",N,&k);
for(int i=strlen(N)-1,j=1;i>=0;i--,j++)
n.s[j]=N[i]-'0';
ans.s[1]=1;
a=n;
for(now=1;now<=k;now++)
{
b=n;
tmp=b.s[now];
int len=0;
do
{
mult1(a,b,b,k);
len++;
}while(len<10&&b.s[now]!=tmp);
if (b.s[now]!=tmp)

{
printf("-1");
return 0;
}
b=a;
for(int i=1;i<=len-1;i++)

mult1(a,b,a,k);
mult2(ans,len,ans);
}

int out;
for(out=200;ans.s[out]==0;out--);
for(;out>=1;out--)
printf("%d",ans.s[out]);
return 0;
}

• @ 2014-12-23 15:36:34

type use=array[1..1000] of integer;var n:string;
meen,realk:integer;
num1,ans,need:use;
procedure init;
var inite,k:string;
space,error,for1:integer;
space:=pos(' ',inite);
n:=copy(inite,1,space-1);
k:=inite; delete(k,1,space);
val(k,realk,error);
if length(n)>=for1 then delete(n,1,length(n)-realk);
for for1:=realk downto 1 do if length(n)>=for1
then num1[realk-for1+1]:=ord(n[for1])-48 else num1[realk-for1+1]:=0;
end;
procedure mult(var a:use;b:use;k1,k2:integer);
var for1,for2,x,y,m:integer;

c:array[1..100] of integer;
begin
fillchar(c,Sizeof(c),0);
if k1>k2 then m:=k1 else m:=k2;
for for1:=1 to k1 do for for2:=1 to k2 do
begin

x:=a[for1]*b[for2];
y:=c[for1+for2-1];
if for1+for2-1<=m then c[for1+for2-1]:=(x+y) mod 10;
if for1+for2<=m then c[for1+for2]:=c[for1+for2]+(x+y) div 10;
end;
for for1:=1 to m do a[for1]:=c[for1];
end;
procedure TheWrongWay;
begin
writeln(-1);
halt;
end;
procedure working;
var for1,for2,for3,box,new:integer;

num2,num3,rp:use;

find:array[0..9] of boolean;

Yes:boolean;
begin

fillchar(need,Sizeof(need),0);
for for1:=1 to realk do
begin

if for1=1 then
begin
ans[1]:=1;
new:=1;
fillchar(num3,Sizeof(num3),0);
for for2:=1 to realk do num3[for2]:=num1[for2];
end;
fillchar(num2,Sizeof(num2),0);
for for2:=1 to realk do num2[for2]:=num3[for2];
if for1>1 then for for2:=1 to (need[for1-1])-1 do
mult(num3,num2,realk,realk);
for for2:=1 to for1 do
num2[for2]:=num1[for2];

new:=0;
fillchar(find,Sizeof(find),false);
box:=num2[for1];
find[box]:=true;Yes:=false;
repeat inc(new);

mult(num2,num3,for1,for1);
if not find[num2[for1]] then find[num2[for1]]:=true
else
begin

if num2[for1]<>box then TheWrongWay
else Yes:=true;
end;

until Yes;

need[for1]:=new;
fillchar(rp,Sizeof(rp),0);

if new=10 then
begin
rp[2]:=1;

rp[1]:=0;

end
else rp[1]:=new;
mult(ans,rp,100,2);
end;
end;
procedure print;
var for1,for2:integer; begin for1:=100;

while ans[for1]=0 do dec(for1);

for for2:=for1 downto 1 do write(ans[for2]);

writeln;
end;
begin
init;
working;
print;
end.

• @ 2009-11-04 18:31:21

各位注意，答案是高精，太阴了！

害我交了两次....

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

type

arra=record

da:array[0..210]of longint;

l:longint;

end;

var

k:longint;n,r:arra;

function min(a,b:longint):longint;

begin

if alength(s1) then q:=length(s1) else q:=k;

for i:=1 to q do

begin

n.da[i]:=ord(s1[length(s1)-i+1])-ord('0');

end;

n.l:=k;

fillchar(r,sizeof(r),0);

for i:=1 to n.l do r.da[i]:=n.da[i];

r.l:=k;

while (r.da[r.l]=0)and(r.l>1) do dec(r.l);

end;

function check(a,r:arra;k:longint):boolean;

var

i:longint;

begin

for i:=1 to k do

begin

if a.da[i]r.da[i] then exit(false);

end;

exit(true);

end;

procedure mult(a,b:arra;var r:arra);

var

i,j:longint;c:arra;

begin

fillchar(r,sizeof(r),0);

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

for i:=1 to min(a.l,k) do

for j:=1 to min(b.l,k) do

begin

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

if c.da>=10 then

begin

c.da:=(c.da div 10)+c.da;

c.da:=c.da mod 10;

end;

end;

for i:=1 to k do r.da[i]:=c.da[i];

r.l:=k;

end;

procedure accmult(a:arra;b:longint;var c:arra);

var

i:longint;

begin

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

c.l:=a.l+2;

for i:=1 to c.l do

begin

c.da[i]:=a.da[i]*b+c.da[i];

if c.da[i]>=10 then

begin

c.da:=(c.da[i] div 10)+c.da;

c.da[i]:=c.da[i] mod 10;

end;

end;

while (c.da[c.l]=0)and(c.l>1) do dec(c.l);

end;

procedure find;

var

i,j,times:longint;b:boolean;c,m,d,z:arra;

begin

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

m:=n;

c.l:=k;

fillchar(z,sizeof(z),0);

z.l:=1;z.da[1]:=1;

if (r.l=1)and(r.da[1]=0) then

begin

writeln(1);

halt;

end

else

for i:=1 to k do

begin

times:=1;

repeat

c:=r;

mult(r,n,r);

mult(c,m,d);

inc(times);

b:=check(m,d,i);

until (b)or(times>10);

if b then

begin

accmult(z,times-1,z);

n:=c;

r:=c;

n.l:=k;

end

else

begin

writeln(-1);

halt;

end;

end;

for i:=z.l downto 1 do write(z.da[i]);

end;

begin

init;

find;

end.

• @ 2021-08-28 12:11:23
``````#include<bits/stdc++.h>
using namespace std;

int xh[11]={1,1,4,4,2,1,1,4,4,2};
int k,b[205],c[205],d[205],p[205],q[205],ss[205],tot1,tot2=2,t;
char a[105];
void mul1(int x[],int y[],int z[])
{
for(int i=1; i<=k; i++)
for(int j=1; j<=k; j++){
z[i+j-1]+=x[i]*y[j];
z[i+j]+=z[i+j-1]/10;
z[i+j-1]%=10;
}
}

void mul2(int x[],int y,int z[])
{
for(int i=1; i<=k; i++){
z[i]+=x[i]*y;
z[i+1]+=z[i]/10;
z[i]%=10;
}
}

int main()
{

scanf("%s%d",a+1,&k);
int len=strlen(a+1);
for(int i=len; i>=len-k+1; i--)
c[++tot1]=a[i]-'0';
for(int i=1; i<=k; i++)
b[i]=c[i];
for(int i=1; i<xh[c[1]]; i++)
{
memset(d,0,sizeof(d));
mul1(b,c,d);
for(int j=1; j<=k; j++)
b[j]=d[j];
}
ss[1]=xh[c[1]];
for(int i=1; i<=k; i++)
q[i]=p[i]=b[i];
while(tot2<=k)
{
for(int i=1; i<=k; i++)
b[i]=c[i];
while(t<11)
{
memset(d,0,sizeof(d));
mul1(b,p,d);
t++;
for(int i=1; i<=k; i++)
b[i]=d[i];
if(b[tot2]==c[tot2])
break;
memset(d,0,sizeof(d));
mul1(q,p,d);
for(int i=1; i<=k; i++)
q[i]=d[i];
}
if(t==11){
cout<<-1;
return 0;
}
for(int i=1; i<=k; i++)
p[i]=q[i];
memset(d,0,sizeof(d));
mul2(ss,t,d);
for(int i=1; i<=100; i++)
ss[i]=d[i];
tot2++;t=0;
}
int len1=105;
while(ss[len1]==0 && len1>1)
len1--;
for(int i=len1; i>=1; i--)
cout<<ss[i];
return 0;
}
``````
• @ 2019-07-17 18:40:09

# 状态 耗时 内存占用

#1 Accepted 1ms 212.0 KiB
#2 Accepted 1ms 228.0 KiB
#3 Accepted 1ms 220.0 KiB
#4 Accepted 1ms 228.0 KiB
#5 Accepted 1ms 224.0 KiB
#6 Accepted 1ms 232.0 KiB
#7 Accepted 1ms 228.0 KiB
#8 Accepted 1ms 228.0 KiB
#9 Accepted 1ms 224.0 KiB
#10 Accepted 1ms 228.0 KiB

没想到速度这么快？！就跟直接打数据一般。

想清楚几点就简单了。
1.循环是从1开始，找到下一个与第一个位置相同的地方就算成功了。（之前做成了，从中途某一个地方开始之后发生循环。然后有个数据会被找到循环数）
2.虽然是找末K位，但是显然的，只要末K位的产生了循环，其末K-1位一定也是循环。反之也即是，K-1位达成了循环后（假设循环次数为N），那么如果有循环产生，那么循环一定是N的倍数。因此算法可以用类似数学归纳法的方式来进行求解。
3.答案很大，要高精。
4.速度快可能是因为用的指针的关系？

PS.终于报了当年的一箭之仇，没错，这是我那年的考题。。。

• @ 2017-03-18 14:37:59

高精度的题目为什么不用python？

``````n , k = [int(i) for i in raw_input().split()]
ans = 1
mod = 1
m = 10 ** k
flag = True
for i in range(k):
mod *= 10
t = ans
a = n
while (n * a % mod) != (a % mod):
ans += t
n = n * a % m
if ans > t * 10:
print("-1")
flag = False
break
if not flag:
break
if flag:
print(ans)
``````
• @ 2018-03-21 22:25:31

因为考试不让用Python

• @ 2021-08-11 23:22:20

因为我不会~

• @ 2014-10-18 21:51:52

###Block Code
#include <cstdio>
#include <cstring>
#include <algorithm>
int n, k, ans[110];
struct Num {
int len, a[110];
Num() {
this->len = 1;
memset(this->a, 0, sizeof(this->a));
}
int& operator {
return this->a[i];
}
};
void copyNum(Num& a, Num b, int k = -1) {
int i;
k = (k == -1) ? b.len : k;
a.len = std::min(b.len, k);
memset(a.a, 0, sizeof(a.a));
for(i = 1; i <= k; i++) {
a[i] = b[i];
}
}
void setString(Num& a, const char * str, int k = -1) {
int i, n = strlen(str);
k = (k == -1) ? n : k;
memset(a.a, 0, sizeof(a.a));
for(i = 1; i <= n && i <= k; i++) {
a[i] = str[n - i] - '0';
}
a.len = k;
}
Num multiK(Num a, Num b, int k) {
int i, j, ij;
Num c;
for(i = 1; i <= k; i++) {
for(j = 1; i + j - 1 <= k; j++) {
ij = i + j - 1;
c[ij] += a[i] * b[j];
if(c[ij] > 9) {
if(ij < k) {
c[ij + 1] += c[ij] / 10;
}
c[ij] %= 10;
}
}
}
c.len = k;
while(c[c.len] == 0) {
c.len--;
}
return c;
}
Num multi(Num a, int b) {
int i, x = 0;
Num c;
copyNum(c, a);
for(i = 1; i <= c.len; i++) {
c[i] = c[i] * b + x;
x = c[i] / 10;
c[i] %= 10;
if(i == c.len && x > 0) {
c.len++;
}
}
return c;
}
int main() {
int k, i, j, tmp;
char str[110];
Num x, y, xx, result;
scanf("%s%d", str, &k);
setString(x, str, k);
setString(result, "1");
copyNum(xx, x, k);
for(i = 1; i <= k; i++) {
copyNum(y, xx, i);
j = y[i];
tmp = 0;
do {
copyNum(y, multiK(y, x, i), k);
tmp++;
} while(tmp < 10 && y[i] != j);
if(j != y[i]) {
printf("-1\n");
return 0;
}
copyNum(y, x, k);
for(j = 1; j < tmp; j++) {
copyNum(x, multiK(x, y, k));
}
copyNum(result, multi(result, tmp));
}
for(i = result.len; i >= 1; i--) {
printf("%d", result[i]);
}
printf("\n");
return 0;
}
cpp版调试N+1次在Codevs上过了来Vijos再测测
强烈鄙视楼上打表

• @ 2013-12-11 21:34:17

曾经n次想过此题，但都是wa了
在本地写过n次，调了n次
最后终于

__测试数据 0: Accepted, time = 0 ms, mem = 440 KiB, score = 10

__测试数据 1: Accepted, time = 0 ms, mem = 436 KiB, score = 10

__测试数据 2: Accepted, time = 0 ms, mem = 436 KiB, score = 10

__测试数据 3: Accepted, time = 62 ms, mem = 440 KiB, score = 10

__测试数据 4: Accepted, time = 0 ms, mem = 444 KiB, score = 10

__测试数据 5: Accepted, time = 62 ms, mem = 432 KiB, score = 10

__测试数据 6: Accepted, time = 62 ms, mem = 440 KiB, score = 10

__测试数据 7: Accepted, time = 46 ms, mem = 444 KiB, score = 10

__测试数据 8: Accepted, time = 78 ms, mem = 436 KiB, score = 10

__测试数据 9: Accepted, time = 93 ms, mem = 436 KiB, score = 10

细节永远是重要的。
#code：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
typedef char big[105];
big now,now2,now3,time,ans,ans2,now4;/*now2:now3*now,
now3:time^now4*/
int l;
void smlt1(char *a,char *b,char *c)
{
int static i;
void smlt2(char *a,int b,char *c,int num);
memset(c,'0',sizeof(char)*104); (c+104) = 0;
for (i = 0;
(b+i) && i < 105;i++)
smlt2(a,(*(b+i))-'0',c+i,i);
*(c+104) = 0;
}
void smlt2(char *a,int b,char *c,int num)
{
int static tmp1,tmp2;
tmp1 = tmp2 = 0;
while ((*a) && (num < l)) {
tmp1 = (*a)-'0';
tmp2 += tmp1*b;
if (*c) {
tmp2 = tmp2-'0'+*c;
*c = '0'+tmp2%10;
} else {
*c = '0'+tmp2%10;
}
tmp2 /= 10;
a++,c++;
num++;
}
while ((tmp2) && (num < l)) {
if (*c) {
tmp2 = tmp2-'0'+*c;
*c = '0'+tmp2%10;
} else {
*c = '0'+tmp2%10;
}
tmp2 /= 10;
c++;
num++;
}
}
int check(int k)
{
smlt1(now4,time,now3);
strcpy(now4,now3);
smlt1(now3,now,now2);
if (now[k] == now2[k])
return 1;
else
return 0;
}

void print_big(char *s)
{
char *p;
p = strlen(s)+s-1;
while (p > s) {
if ((*p) != '0')
break;
p--;
}
while (p >= s) {
printf("%c",*p);
p--;
}
printf("\n");
}

void clear1(char *s)
{
memset(s,0,sizeof(char)*105);
*s = '1';
}

int main()
{
int i,j;

void init();

init();
for (i = 0;i < l;i++) {
strcpy(time,now3);
clear1(now4);
for (j = 1;j <= 10;j++)
if (check(i) == 1)
break;
if (j != 11) {
memset(ans2,0,sizeof(char)*105);
smlt2(ans,j,ans2,0);
strcpy(ans,ans2);
if (i == l-1)
break;
} else {
printf("-1\n");
return 0;
}
}
print_big(ans);
return 0;
}

void reverse(char *s)
{
char *p,ch;
p = strlen(s)+s-1;
while (p > s) {
ch = *p; *p = *s; *s = ch;
p--; s++;
}
}

void init()
{
memset(now2,0,sizeof(char)*105);
memset(now3,0,sizeof(char)*105);
memset(time,0,sizeof(char)*105);
memset(ans,0,sizeof(char)*105);
memset(ans2,0,sizeof(char)*105);
memset(now4,0,sizeof(char)*105);
scanf("%s",now);
reverse(now);
strcpy(now3,now); strcpy(now2,now);
scanf("%d",&l);
memset(ans,'0',sizeof(ans));
ans[0] = '1'; ans[104] = 0;
ans2[0] = '1'; ans2[104] = 0;
}

• @ 2013-10-29 20:18:31

虽然过了,但还是不理解,希望以后有能力了,再来重新刷吧.
DXe-SYF

• @ 2013-10-18 21:06:46

测试数据 #0: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 824 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 828 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 824 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 828 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 824 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 828 KiB, score = 10
测试数据 #8: Accepted, time = 78 ms, mem = 828 KiB, score = 10
测试数据 #9: Accepted, time = 78 ms, mem = 824 KiB, score = 10
Accepted, time = 434 ms, mem = 828 KiB, score = 100

3小时...连普及组的题都做得这么艰辛的我真是蒟蒻..

• @ 2013-10-07 01:23:47

测试数据 #0: Accepted, time = 15 ms, mem = 736 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 736 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 732 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 736 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 732 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 732 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 736 KiB, score = 10
测试数据 #8: Accepted, time = 62 ms, mem = 736 KiB, score = 10
测试数据 #9: Accepted, time = 62 ms, mem = 736 KiB, score = 10

• @ 2013-04-08 11:41:26

#include<iostream>
#include<string>
#include<string.h>
#include<cstdlib>
using namespace std;
string s;
int k;
int a[101],b[101],w[101]={0};
int gw[10]={1,1,4,4,2,1,1,4,4,2};
int cheng[101]={0},bei[101]={0};
void init()
{
int i;
cin>>s>>k;
w[0]=gw[s[s.length()-1]-'0'];
for(i=0;i<s.length();i++)
a[s.length()-i-1]=s[i]-'0';
}
void multi(int a[],int b[])
{
int i,j;
int c[101];
memset(c,0,sizeof(c));
for(i=0;i<100;i++)
for(j=0;j<100;j++)
if(i+j<100)
{
c[i+j]+=a[i]*b[j];
c[i+j+1]+=c[i+j]/10;
c[i+j]=c[i+j]%10;
}
for(i=0;i<100;i++)
{
c[i+1]+=c[i]/10;
c[i]=c[i]%10;
}
memcpy(b,c,sizeof(c));
}
int bj(int a[],int b[],int n)
{
int i;
for(i=0;i<=n;i++)
if(a[i]!=b[i])
return 0;
return 1;
}

void solve()
{
int i,j;
int temp[101]={0};
bei[0]=1;
for(i=0;i<w[0];i++)
{
multi(a,bei);
}
for(i=1;i<k;i++)
{
memcpy(cheng,a,sizeof(a));
memset(temp,0,sizeof(temp));
temp[0]=1;
for(j=1;j<=10;j++)
{
multi(bei,cheng);
multi(bei,temp);
if(bj(cheng,a,i)==1)
{
w[i]=j;
memcpy(bei,temp,sizeof(temp));
break;
}
}
if(w[i]==0)
{
cout<<-1<<endl;
exit(0);
}

}

}
void dmulti(int a[],int b)
{
int i;
int c[101];
memset(c,0,sizeof(c));
for(i=0;i<100;i++)
{
c[i]+=a[i]*b;
c[i+1]+=c[i]/10;
c[i]=c[i]%10;
}
memcpy(a,c,sizeof(c));
}
void print()
{
int i,j;
int ans[101]={0};
ans[0]=1;
for(i=0;i<k;i++)
dmulti(ans,w[i]);
i=100;
while((ans[i]==0)&&(i>0))i--;
for(j=i;j>=0;j--)cout<<ans[j];
}
int main()
{
init();
solve();
print();
return 0;
}

• @ 2013-02-16 10:14:47
• @ 2009-10-05 12:15:44

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

• @ 2009-10-01 00:19:58

编译通过...

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

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

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

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

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

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

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

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

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

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

没有任何优化...

没想到普及组还有这么难的题目...

做了我半年......

• @ 2018-08-19 08:03:24

那么久

• @ 2009-09-28 11:41:01

MD,本说随便找一道题来强J，结果反被强J！

耻辱啊....

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

• @ 2009-09-21 01:09:00

按位数逐渐递增的试探

如果前i位的循环长度是k

那么前i+1位的循环长度必为k的倍数,假设这个倍数为p

用数论知识可以证明,如果p大于10那么,一定无解.

只要用高精度乘法模拟,

欧拉函数,快速幂什么的都可以不用

要注意,高精要写两个,

一个是试探循环长度的高精,只要乘k位

另一个是答案的高精度乘法,因为只要乘p,p小于10,

所以第二个乘法是单精度的,位数显然都要算.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

这个是Vijos Sunny

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

这个是Vivid Puppy

速度差这么多..

• @ 2020-02-09 10:51:20

#include<cstdio>
#include<cstring>
char c[109];int k,l,u;
struct big{int a[109];}d,p,q,r,s,t;
big mul(big x,big y){big z=d;int i,j;for(i=1;i<=k;++i){
for(j=k-i+1;j;--j){z.a[i+j-1]+=x.a[i]*y.a[j];}
}for(i=1;i<k;++i)z.a[i+1]+=z.a[i]/10,z.a[i]%=10;
z.a[k]%=10;return z;}
int main(){
int i,j;scanf("%s%d",c,&k),l=strlen(c);
for(i=(l<k?l:k);i;--i)p.a[i]=c[l-i]-48;r=p,t.a[l=1]=1;
for(i=1;i<=k;++i){if(mul(p,r).a[i]==p.a[i])continue;u=1,s=r;
do{r=mul(s,r),++u;if(u>10){puts("-1");
return 0;}}while(mul(p,r).a[i]!=p.a[i]);for(j=1;j<=l;++j)t.a[j]*=u;
for(j=1;j<l;++j)t.a[j+1]+=t.a[j]/10,t.a[j]%=10;if(t.a[l]>=10)t.a[l+1]+=t.a[l]/10,t.a[l++]%=10;
}for(i=l;i;--i)printf("%d",t.a[i]);}

• @ 2018-11-27 08:28:59

卢本伟牛逼

• @ 2018-10-13 10:44:39

一道非常恶心的题目
高精题

``````#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int note[202],b[202],pd[202],ans[1001],q[202];
int k,w,len;
char s[202];
{
int res=0,f=1,ch;
while(ch<'0'||ch>'9'){ch=getchar();if(ch=='-') f=-1;}
while(ch>='0'&&ch<='9') res=res*10+ch-48,ch=getchar();
return res*f;
}
inline void write(int x){   if(x==0){putchar(48);return;}   int len=0,dg[20];   while(x>0){dg[++len]=x%10;x/=10;}   for(int i=len;i>=1;i--)putchar(dg[i]+48);}
inline void work()
{
memset(q,0,sizeof(q));
for(register int i=1; i<=k; i++)
for(register int j=1; j<=k; j++)
{
if(i+j-1<=k)
q[i+j-1]+=b[i]*pd[j];
else
break;
}
for(register int i=1; i<=k; i++)
{
if(q[i]>=10)
{
q[i+1]+=q[i]/10;
q[i]%=10;
if(i+1>k)q[i+1]=0;
}
}
}
inline void di(int x)
{
for(register int i=1; i<=ans[0]; i++)
{
ans[i]=ans[i]*x;
}
for(register int i=1; i<=ans[0]; i++)
{
if(ans[i]>=10)
{
ans[i+1]+=ans[i]/10;
ans[i]%=10;
if(i+1>ans[0])
ans[0]++;
}
}
}
int main()
{
w=1;
len=strlen(s);
for(register int i=1; i<=k; i++)
{
b[i]=note[i]=s[len-i]-'0';
}
ans[0]=ans[1]=1;
while(w<=k)
{
memset(pd,0,sizeof(pd));
pd[1]=1;
work();
swap(q,pd);
int n=b[w];
for(register int i=1; i<=11; i++)
{
work();
if(q[w]==n)
{
di(i);
swap(b,pd);
break;
}
swap(q,pd);
if(i==11) {
printf("-1");
return 0;
}
}
w++;
}
for(register int i=ans[0]; i>=1; i--)
write(ans[i]);
return 0;
}
``````

ID
1032

7

4012

848

21%

22