JZOJ_7.18 Cグループの第2題の運が悪い小さいC

に言及
nを与え,毎回(n,(−1)i+1∗i)(n,(−1)i+1∗i)のベクトルを描き,合計n個のベクトルを描き,このパターンがいくつかの格子点を通過することを求めた.
構想
観察すると,(n,i)(n,i)のベクトルを描くたびに通過する格子点数はgcd(i,n)g c d(i,n)であるため,Σi=1 ngcd(i,n)Σi=1 n g c d(i,n)となるが,このようにするとタイムアウトする.したがって,問題解によりΣd|nd∗に簡略化できることが分かった.φ(n/d) ∑ d | n d ∗ φ (n/d)、(√n)(n)まで列挙し、n/i n/iで別の数を得ることができ、完全な平方数は特殊に判断しなければならない.具体的な原理はよく分からない.
コード#コード#

#include
#include
#include
using namespace std;
long long n,ans;
inline long long phi(long long n)//     
{
    long long tot=n;
    for (long long i=2;i<=sqrt(n);i++)
        if (n%i==0)
        {
            tot=tot/i*(i-1);
            while (n%i==0) n/=i;
        }
    if (n>1) tot=tot/n*(n-1);
    return tot;
}
int main()
{
    scanf("%lld",&n);
    for (long long i=1;i<=sqrt(n);i++)
    {
        if (n%i==0)
        {
            ans+=i*phi(n/i);
            if (i*i!=n) ans+=n/i*phi(i);
        }
    }
    printf("%lld",ans+1);//    (0,0)
}