题目描述
计算,有多组数据。
输入格式
一个正整数T表示数据组数。
接下来T行 每行两个正整数 表示N、M。(T <= 10000;N, M<=10000000)
输出格式
共T行,每行一个整数 表示第i组数据的结果。
题目解析
膜拜神犇PoPoQQQ。
将最小公倍数转化为我们熟悉的最大公约数,有
设,则有
那怎样高效地求出呢?
令,可得
我们只需求出的前缀和,即可在单次
的复杂度下求出
函数,于是总复杂度是
。
至此,我们已经可以解决本题的弱化版[BZOJ 2154] Crash的数字表格。但本题有多组数据,我们尝试将复杂度优化到单次询问。我们把
函数在原式展开:
于是我们只需要求出的前缀和即可在
解决问题。我们来分析这个函数,可以发现
是
和
的狄利克雷卷积,由于
和
均为积性函数,故
为积性函数,可以线性筛。
最终的总复杂度为。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
/************************************************************** Problem: 2693 User: frank_c1 Language: C++ Result: Accepted Time:3832 ms Memory:245412 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=(int)(1e7)+5; const int maxv=(int)(1e7); const int mo=100000009; bool check[maxn]; int pr[maxn],mu[maxn]; LL val[maxn],sum[maxn]; int tot; void gen_table() { memset(check,0,sizeof(check)); int n=maxv; val[1]=sum[1]=1; for(int i=2;i<=n;i++) { if(!check[i]) { pr[++tot]=i; val[i]=1ll*i*(1-i) % mo; } for(int j=1;j<=tot;j++) { if(i*pr[j]>n) break; check[i*pr[j]]=1; if(i%pr[j]==0) { val[i*pr[j]]=val[i]*pr[j] % mo; break; } else val[i*pr[j]]=val[i]*val[pr[j]] % mo; } sum[i]=(sum[i-1]+val[i]+mo) % mo; } } inline LL g(LL n,LL m) { return ((n*(n+1)/2) % mo)*((m*(m+1)/2) % mo) % mo; } int main() { int T; read(T); gen_table(); while(T--) { int n,m,pos; LL res=0; read(n);read(m); for(int i=1;i<=min(n,m);i=pos+1) { pos=min(n/(n/i),m/(m/i)); res=(res+1ll*(sum[pos]-sum[i-1]+mo)*g(n/i,m/i)) % mo; } printf("%lld\n",res); } return 0; } |