[BZOJ 2190][SDOI 2008]儀仗隊-オラ関数

明らかに長さと幅が互いに分かれば見えます.
だから1~n-1のオーラ関数和だけを要求して、*2+1でよい

#include"iostream"
#include"stdio.h"
using namespace std;
int n,eular[40005],prime[10005],ans,tmp;
void Eular(){
    eular[1]=1; int i,j;
    for (i=2;i<=n;i++)
    { 
        if (eular[i]==0) 
        {   
            prime[++tmp]=i;
            eular[i]=i-1;
            if(i*i<=n)
             eular[i*i]=i*i-i;
        }
        for (j=1;j<tmp&&i*prime[j]<=n;j++) 
        {
            if(i%prime[j])
             eular[i*prime[j]]=eular[i]*eular[prime[j]];
            else
             eular[i*prime[j]]=eular[i]*prime[j]; 
        }
    }
    for (i=1;i<n;i++) ans+=eular[i];
}
int main(){
    cin>>n; int i; Eular();
    cout<<ans*2+1<<endl;
    return 0;
}