冬休み合宿にテーマをつけてレポートを解说します。
1281 ワード
この問題に腹を立てて死にそうだ。いつもTLE、T泥炭ですね!長い間考えましたが、どうやって最適化するか分かりません。0を入力しても出てこないですね!!!!!
http://acm.sdut.edu.cn:8080/judge/contest/view.action?cid=5#problem/E
最初はそんなに多く考えていませんでした。10000桁でも最大の数字9です。彼らの合計は9999にすぎません。その後、ans+=sum%10です。sum/=10いいです。だから最初のコードは以下の通りです。
http://acm.sdut.edu.cn:8080/judge/contest/view.action?cid=5#problem/E
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[10010];
int main()
{
while(scanf("%s",a)&&strcmp(a,"0")!=0)
{
int sum=0;
for(int i=0;i<=strlen(a)-1;i++)
{
sum+=a[i]-'0';
}
if(sum%9==0){cout<<"9"<<endl;}
else {cout<<sum%9<<endl;}
}
}
考え方は正常で、最後に9の型を取ってGCDで証明すればいいです。詳しくは「初等数論」を参照してください。最初はそんなに多く考えていませんでした。10000桁でも最大の数字9です。彼らの合計は9999にすぎません。その後、ans+=sum%10です。sum/=10いいです。だから最初のコードは以下の通りです。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[10010];
int main()
{
while(scanf("%s",a)&&strcmp(a,"0")!=0)
{
int sum=0;
for(int i=0;i<=strlen(a)-1;i++)
{
sum+=a[i]-'0';
}
int ans=0;
while(sum>=1)
{
ans+=sum%10;
sum/=10;
}
cout<<ans<<endl;
}
}