1325: A very hard problem
Time Limit: 3 Sec Memory Limit: 160 MB
Submit:
203 Solved: 53
[Submit][Status][Web
Board]
Description
CX老湿经常被人黑，被黑得多了，自己也就麻木了。于是经常听到有人黑他，他都会深情地说一句：禽兽啊！
一天CX老湿突发奇想，给大家出了一个难题，并且声称谁能够准确地回答出问题才能继续黑他，否则他就要反击了。
这个难题就是：
给出两个数p和q，接下来q个询问，每个询问给出两个数A和B，请分别求出：
一、有多少个有序数对（x，y）满足1<=x<=A，1<=y<=B，并且gcd（x，y）为p的一个约数；
二、有多少个有序数对（x，y）满足1<=x<=A，1<=y<=B，并且gcd（x，y）为p的一个倍数。
Input
只有一组测试数据。
第一行两个数：p和q。（1<p<10^7 ，1<q<1000。）
接下来有q行，每行两个数A和B。（1<A,B<10^7）
Output
输出共q行。每行两个数。用空格隔开。
分别表示题目描述中的两个对应的答案。
(x,y)=(2,3)和(x,y)=(3,2)被视为两个不同有序数对哦！
Sample Input
6 3
8 8
15 32
13 77
Sample Output
58 1
423 10
883 24
HINT
对于64位整型请用lld，或者cin，cout。T_T
CSU_LQ
这一道题是去年的一次比赛的题，当时觉得用欧拉能做，然后很难实现。
后来知道用莫比乌斯反演来做，但是一直超时。已经使用分块了，还是超时。
题意：略
思路：对于第二种，直接(A/p)*(B/p)就是答案。不难理解。
对于第一种情况：
设
g(p)代表枚举P的每一因子 di 求gcd(x,y)=di (1<=x<=A,1<=y<=B)的累加和。
就是题意要求的值。
如果此时，枚举每一个P的因子di 来求，就会超时。
这个式子可以转化一下，另T = di*x,那么式子可以转化为：
这样的话，我们只需要先预处理后一部分，就可以用sqrt(min(A,B)) 的时间解决这个问题。
这部分如何预处理呢？
首先我们先打表求出u[];
分析这个式子，设tom(T) = sigma(u[di],T%di==0&&di是P的因子);
由于p是唯一的，我们求出它的因子，然后用它的因子筛选一下数组hxl[ ] ,就是tom（T）；
最后hxl[]，前n项和，用分块来做，完毕。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<math.h>
using namespace std; typedef long long LL;
const int maxn = 1e7+;
bool s[maxn];
int prime[],len = ;
int yz[],ylen;
int mu[maxn];
int hxl[maxn];
void init()
{
memset(s,true,sizeof(s));
mu[] = ;
for(int i=;i<maxn;i++)
{
if(s[i] == true)
{
prime[++len] = i;
mu[i] = -;
}
for(int j=;j<=len && ((long long)prime[j])*i<maxn;j++)
{
s[i*prime[j]] = false;
if(i%prime[j]!=)
mu[i*prime[j]] = -mu[i];
else
{
mu[i*prime[j]] = ;
break;
}
}
}
}
void solve(int p)
{
ylen = ;
int k = (int)sqrt(p*1.0);
int tmp;
for(int i=;i<=k;i++)
{
if(p%i==)
{
yz[++ylen] = i;
tmp = p/i;
if(tmp!=i) yz[++ylen] = tmp;
}
}
for(int i=;i<=ylen;i++)
{
for(int j=yz[i],k=;j<maxn;j=j+yz[i],k++)
hxl[j]=hxl[j]+mu[k];
}
for(int i=;i<maxn;i++) hxl[i] = hxl[i]+hxl[i-];
}
int main()
{
init();
int p,q,A,B;
scanf("%d%d",&p,&q);
solve(p);
while(q--)
{
scanf("%d%d",&A,&B);
if(A>B) swap(A,B);
long long ans1 = ,ans2 = ;
for(int i=,la = ;i<=A; i=la+)
{
la = min(A/(A/i),B/(B/i));
ans1 = ans1+(long long)(hxl[la]-hxl[i-])*(A/i)*(B/i);
}
ans2 = (A/p)*(B/p);
printf("%lld %lld\n",ans1,ans2);
}
return ;
} /**************************************************************
Problem: 1325
User: 987690183
Language: C++
Result: Accepted
Time:1052 ms
Memory:92044 kb
****************************************************************/