hdu 4466 Triangle - c++编程基础

对于长度为n的三角形的个数是靠打表找出来的规律，就不解释了。

然后这个三角形最大公约数为1，那么就可以用筛选法来做。

最后计算答案就o(n)扫描的计算，这个比较简单，不解释了。

#include   
#include   
#include   
using namespace std;  
const int maxn=5e6+111,mod=1e9+7,N=5e6;  
int sum[maxn],p[maxn];  
  
void getsum()  
{  
    for(int i=3,tmp;i<=N;i++)  
    {  
        tmp=i-2;  
        sum[i]=sum[i-1];  
        if(tmp&1)  
        {  
            sum[i]+=tmp/6+((tmp%6)!=0);  
        }  
        else  
        {  
            sum[i]-=tmp/12+((tmp%12)!=0);  
            if(tmp%12==4)  
            sum[i]++;  
        }  
        sum[i]%=mod;  
    }  
}  
  
void getdp()  
{  
    for(int i=3;i<=N;i++)  
    for(int j=i+i;j<=N;j+=i)  
    {  
        sum[j]=sum[j]-sum[i];  
        if(sum[j]<0) sum[j]+=mod;  
    }  
}  
  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    p[0]=1;  
    for(int i=1;i<=N;i++)  
    p[i]=(p[i-1]*2)%mod;  
    getsum();  
    getdp();  
    int n,tt=0;  
    while(scanf("%d",&n)!=EOF)  
    {  
        long long ans=0;  
        for(int i=1;i<=n;i++)  
        if(n%i==0)  
        {  
            ans+=(long long)p[n/i-1]*sum[i];  
            ans%=mod;  
        }  
        printf("Case %d: %I64d\n",++tt,ans);  
    }  
    return 0;  
}