@OceanEye7年前
04/13
21:39
nlogn狄利克雷卷积打表
和普通的差不多，就是和换成积，贡献算一算就可以了
然后死活想不起来 写 O(n根号n) 的TLE到死
安利 金策大爷 的教程
贴完代码跑路qwq
|
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 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #define ll long long #define p(x) ('0'<=x&&x<='9') char cc; void read(int &x) { cc=getchar(); x=0; while(!p(cc)) cc=getchar(); while(p(cc)) { x=x*10+cc-48; cc=getchar(); } } using namespace std; #define M 1000000 #define mod 1000000007 void ext__(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return; } ext__(b,a%b,y,x); y-=(a/b)*x; } int pow_mod(int a,ll b) { int ret=1; while(b) { if(b&1) ret=(ll)ret*a%mod; a=(ll)a*a%mod; b>>=1; } return ret; } int get_inv(int k) { if(k==1) return 1; int x,y; ext__(mod,k,x,y); return (mod+(y%mod))%mod; } int prime[M+10],miu[M+10],_[M+10],pre[M+10],fib[M+10],tot; bool isprime[M+10]; void init() { fib[0]=0; fib[1]=1; for(int i=2;i<=M;++i) { fib[i]=fib[i-1]+fib[i-2]; if(fib[i]>mod) fib[i]-=mod; } miu[1]=1; _[1]=1; for(int i=2;i<=M;i++) { if(!isprime[i]) { prime[tot++]=i; miu[i]=-1; _[i]=fib[i]; } for(int j=0;j<tot;j++) { if(i*prime[j]>M) break; isprime[i*prime[j]]=true; if(i%prime[j]==0) { miu[i*prime[j]]=0; break; } miu[i*prime[j]]=-miu[i]; } } for(int i=0;i<=M;i++) pre[i]=1; for(int i=1;i*i<=M;i++) { for(int j=i;j*i<=M;j++) if(i==j) { if(miu[i]==-1) pre[i*j]=(ll)pre[i*j]*get_inv(fib[i])%mod; if(miu[i]==1) pre[i*j]=(ll)pre[i*j]*fib[i]%mod; } else { if(miu[i]==-1) pre[i*j]=(ll)pre[i*j]*get_inv(fib[j])%mod; if(miu[i]==1) pre[i*j]=(ll)pre[i*j]*fib[j]%mod; if(miu[j]==-1) pre[i*j]=(ll)pre[i*j]*get_inv(fib[i])%mod; if(miu[j]==1) pre[i*j]=(ll)pre[i*j]*fib[i]%mod; } } for(int i=2;i<=M;i++) pre[i]=(ll)pre[i]*pre[i-1]%mod; } int T,A,B,ans; int main() { init(); for(read(T);T;T--) { ans=1; read(A); read(B); if(A>B) swap(A,B); for(int node=1,m;node<=A;node=m+1) { m=min(A/(A/node),B/(B/node)); ans=(ll)ans*pow_mod((ll)pre[m]*get_inv(pre[node-1])%mod,(ll)(A/node)*(B/node))%mod; } printf("%d\n",ans); } return 0; } |