Training：スクリーニングと前処理

HDU 1215：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=22310 一つの数字n（n≦500000）を与え、nの全ての因子の和aiを出力する。ふるいは表を打って500000以内のすべてのaiを求めます。

#include<cstdio>
using namespace std;
const int maxn=500010;
int n,a[maxn];
int main(){
    for(int i=1;i<maxn;++i)
        for(int j=i+i;j<maxn;j+=i)
            a[j]+=i;
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf("%d
",a[n]);
    }
    return 0;
}

HDU 1286：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=37852 問題解決の報告を書いてやっと分かりました。これは元々オーロラの関数を求めていたのです。Φ（n）の問題ですが、データが水になりました。乱暴しました。自分のコードを貼りません。Euler関数のテンプレートを貼ります。

int phi[maxn]={0,1};
void phi_table (int n) {
    for(int i=2;i<=n;++i) 
    if(!phi[i])
        for(int j=i;j<=n;j+=i) {
            if(!phi[j]) phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
}

HDU 1406：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=36674 完全な数を定義します。1より大きい正の整数のすべての因子の和がその自身に等しい場合、この数は整数です。num 1とnum 2を入力して、両方の完璧な個数を出力します。表をクリックして、すべての因子と、完璧かどうかを判断し、プレフィックスと出力を求めます。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int a[maxn],b[maxn];
int main(){
    for(int i=1;i<maxn;++i)
        for(int j=i+i;j<maxn;j+=i)
            a[j]+=i;
    for(int i=1;i<maxn;++i)
        if(a[i]==i) b[i]=b[i-1]+1;
        else b[i]=b[i-1];
    int t;scanf("%d",&t);
    while(t--){
        int l,r;scanf("%d%d",&l,&r);
        if(l>r) swap(l,r);
        printf("%d
",b[r]-b[l-1]);
    }
    return 0;
}

HDU 2007：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=32827 与えられた一連の整数は、偶数のすべての平方と奇数のすべての立方とを求める。表を打って解く

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2510;
int a[maxn],b[maxn];
int main(){
    for(int i=1;i<maxn;++i){
        a[i]=a[i-1],b[i]=b[i-1];
        if(i&1) a[i]+=i*i*i;
        else b[i]+=i*i;
    }
    int l,r;
    while(~scanf("%d%d",&l,&r)){
        if(l>r) swap(l,r);
        printf("%d %d
",b[r]-b[l-1],a[r]-a[l-1]);
    }
    return 0;
}

HDU 1425:http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21604 n個の数を入力して、大きいから小さい出力までのmの大きさ、数の範囲［−500000、＋500000］を指定します。配列で統計したいのですが、n≦100000のデータ量は、快速O（nlogn）はタイムアウトします。データが水になっても大丈夫です。配列で作ったもので、各数字の出現回数を記録して、大きいものから小さいものまで出力します。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=500010;
int a[maxn*2];
inline int Scan(){
    int res=0,ch,flag=0;
    if((ch=getchar())=='-') flag=1;
    else if(ch>='0'&&ch<='9') res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
    return flag?-res:res;
}
void Out(int k) {
    if(k<0) {putchar('-');k=-k;}
    if(k>=10) Out(k/10);
    putchar(k%10+'0');
}
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        memset(a,0,sizeof(a));
        getchar();
        for(int i=0;i<n;++i){
            int k=Scan();
            ++a[k+maxn];
        }
        bool first=true;
        for(int i=2*maxn-1;i>=0;--i){
            if(!m) break;
            for(int j=a[i];j>0;--j){
                if(first) first=false;
                else putchar(' ');
                Out(i-maxn),--m;
                if(!m)break;
            }
        }
        putchar('
');
    }
    return 0;
}

HDU 2039：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=32836 三つの数を入力して、三角形を構成するかどうかを判断します。簡単な問題ですが、問題では整数とは言わないので、doubleを使います。

#include<cstdio>
using namespace std;
int main(){
    int t;scanf("%d",&t);
    while(t--){
        double a,b,c;
        scanf("%lf%lf%lf",&a,&b,&c);
        puts(a>0&&b>0&&c>0&&a+b>c&&b+c>a&&a+c>b?"YES":"NO");
    }
    return 0;
}

HDU 1170:http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17623 各グループは一つの記号と二つの整数を入力して、このような演算の結果を求めます。簡単な問題ですが、穴があります。除法なら、ゼロを出力しないと出力できません。つまり、1÷10を計算する場合、0.1ではなく0.10を出力します。

#include<cstdio>
using namespace std;
int main(){
    int t;scanf("%d",&t);
    while(t--){
        getchar();
        char c=getchar();
        int a,b;scanf("%d%d",&a,&b);
        if(c=='+') printf("%d",a+b);
        if(c=='-') printf("%d",a-b);
        if(c=='*') printf("%d",a*b);
        if(c=='/'){if(a%b==0)printf("%d",a/b);else printf("%.2lf",1.0*a/b);}
        putchar('
');
    }
    return 0;
}