FZU 2191完璧な数字(暴力的思考)
1725 ワード
今日の練習試合でこの問題があって、最初は暴力で書いて、どのように書いてどのようにタイムアウトします.後で簡単な方法を思いついた.例えば、50~80の流行度の和を求めると、まず1~49の流行度を求め、1~80の流行度を求めることができます.後者は前者を減らすと50~80の流行度の和になります.その中で2つの区間の流行度の和を求めるときには一定のテクニックがあります.テクニックは問題解を見てください.
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
long long x,y;
while(~scanf("%lld%lld",&x,&y))
{
x--;
long long int sum1=0,sum2=0;
for(long long i=1; i*i*i<=x; i++)
{
sum1+=(x/(i*i)-i+1);
}
for( long long j=1; j*j*j<=y; j++)
{
sum2+=(y/(j*j)-j+1);
}
printf("%lld
",sum2-sum1);
}
return 0;
}