记录编号	29854	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题B	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	6.109 s
提交时间	2011-10-26 11:44:25	内存使用	2.43 MiB

#include <cstdio>
#include <cmath>
#define maxn 50000 + 10
 
int p[maxn] = {0};
int f1[maxn] = {0},f2[maxn] = {0};
 
inline void pre()
{
    int i,j,t;
    for( i = 1 ; i <= 50000 ; ++i )
        {
            p[i] = 1;
            for( j = 2, t = i ; j*j <= t && p[i] ; ++j )
                if( !(t % j) )
                    {
                        t /= j;
                        p[i] = -p[i];
                        if( !(t % j) )
                            p[i] = 0;
                    }
            if( t > 1 ) p[i] = -p[i];
        }
    for( i = 2 ; i <= 50000 ; ++i )
        p[i] += p[i-1];
}
 
inline int calc( int a, int b, int d )
{
    int i,j,t;
    a /= d, b /= d;
            
    f1[0] = (int)sqrt(a) * 2;
    for( i = 1 ; i*i <= a ; ++i )
        {
            f1[i] = i;
            f1[f1[0]+1-i] = a/i;
        }
    f2[0] = (int)sqrt(b) * 2;
    for( i = 1 ; i*i <= b ; ++i )
        {
            f2[i] = i;
            f2[f2[0]+1-i] = b/i;
        }
    
    int ans = 0;
    for( i = 1, j = 1, t = 0 ; i <= f1[0] || j <= f2[0] ; )
        {
            if( i <= f1[0] && ( j > f2[0] || f1[i] < f2[j] ) )
                {
                    ans += (p[f1[i]]-p[t])*(a/f1[i])*(b/f1[i]);
                    t = f1[i++];
                }
            else
                {
                    ans += (p[f2[j]]-p[t])*(a/f2[j])*(b/f2[j]);
                    t = f2[j++];
                }
        }
    return ans;
}
 
int main()
{
    int T,Test;
    int a,b,c,d,k;
    
    FILE *fp,*fo;
    fp = fopen("b.in","r");
    fo = fopen("b.out","w");
    
    pre();
    fscanf(fp,"%d",&Test);
    for( T = 1 ; T <= Test ; ++T )
        {
            fscanf(fp,"%d%d%d%d%d",&a,&b,&c,&d,&k);
            fprintf(fo,"%d\n",calc(b,d,k)-calc(b,c-1,k)-calc(a-1,d,k)+calc(a-1,c-1,k));
        }
        
    fclose(fp);
    fclose(fo);
    return 0;
}