冬休み合宿にテーマをつけてレポートを解说します。

1281 ワード

この問題に腹を立てて死にそうだ。いつもTLE、T泥炭ですね!長い間考えましたが、どうやって最適化するか分かりません。0を入力しても出てこないですね!!!!!
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;
    }
}