网站开发后端 书,网站建设一条龙全包seo,网站内页设置多少个关键字最好,永嘉网站制作系统题意 求以下式子的值#xff0c;T组数据各个字母满足1 ≤ n , a , b ≤109 #xff0c;a,b互质 思路#xff1a; 卡常毒瘤题#xff0c;出题人时限卡的非常紧#xff0c;考场上推出来又T又WA 1 #includebits/stdc.h2 using namespace std;3 typedef long long ll;… 题意 求以下式子的值T组数据各个字母满足1 ≤ n , a , b ≤109 a,b互质 思路 卡常毒瘤题出题人时限卡的非常紧考场上推出来又T又WA 1 #includebits/stdc.h2 using namespace std;3 typedef long long ll;4 const int maxn1e610,mod1e97;5 const int inv2500000004,inv3333333336;6 int phi[maxn],n,ans;7 8 vectorint p;bool np[maxn];9 mapint,int Phi;
10
11 void init(){
12 phi[1]1;
13 for(int i2;imaxn;i){
14 if(!np[i]){
15 p.push_back(i);
16 phi[i]i-1;
17 }
18 for(int j0;jp.size()p[j]*imaxn;j){
19 np[i*p[j]]true;
20 if(i%p[j]0){
21 phi[i*p[j]]phi[i]*p[j];
22 break;
23 }
24 phi[i*p[j]]phi[i]*(p[j]-1);
25 }
26 }
27 for(int i1;imaxn;i)
28 phi[i](1ll*phi[i]*i%modphi[i-1])%mod;
29 }
30 int read(){
31 int x0;char cgetchar();
32 for(;!isdigit(c);cgetchar());
33 for(;isdigit(c);cgetchar())x(x3)(x1)(c^48);
34 return x;
35 }
36 void Write(int x){
37 if(x0)return;
38 Write(x/10);putchar(x%100);
39 }
40 void write(int x){
41 if(x0)putchar(0);
42 else Write(x);
43 }
44 int Sum2(int n){
45 int retn;
46 ret(ll)ret*inv2%mod;
47 ret(ll)ret*(n1)%mod;
48 return ret;
49 }
50 int Sum3(int n){
51 int retSum2(n),tmp(2ll*n1)%mod;
52 ret(ll)ret*inv3%mod;
53 ret(ll)ret*tmp%mod;
54 return ret;
55 }
56 int phii(int n){
57 if(nmaxn)return phi[n];
58 if(Phi.count(n))return Phi[n];
59 int retSum3(n);
60 for(int i2,r,tmp;in;ir1){
61 rmin(n,n/(n/i));
62 tmp(ll)phii(n/i)*(Sum2(r)-Sum2(i-1))%mod;
63 ret-tmp;
64 if(ret0)retmod;
65 if(retmod)ret-mod;
66 }
67 return Phi[n]ret;
68 }
69 void solve(){
70 nread();read();read();
71 Phi.clear();
72 ans(phii(n)-1mod)%mod;
73 ans(ll)inv2*ans%mod;
74 write(ans);puts();
75 }
76 int main(){
77 init();
78 int T;scanf(%d,T);
79 for(;T--;)solve();
80 return 0;
81 } 转载于:https://www.cnblogs.com/ndqzhang1111/p/11402780.html
