果然我还是太菜了......
T1:
1 #include2 #include 3 //#include 4 //#define debug cout 5 //using namespace std; 6 typedef long long int lli; 7 const int maxn=5e2+1e1,maxk=22; 8 const int mod=232792561; 9 10 lli f[2][maxn][maxk];11 int n,k;12 13 inline int gcd(int x,int y) {14 register int t;15 while( t = x % y )16 x = y , y = t;17 return y;18 }19 inline int lcm(int x,int y) {20 if( ! ( x && y ) ) return x | y;21 return x / gcd(x,y) * y;22 }23 inline void trans(lli dst[maxn][maxk],const lli sou[maxn][maxk],int now) {24 for(int i=0;i<=n;i++) {25 const int tar = lcm(i,now);26 if( tar > n ) continue;27 for(int j=0;j
正解代码:
1 //#include2 #include 3 #include 4 //#include 5 //#define debug cout 6 typedef long long int lli; 7 //using namespace std; 8 const int maxl=2e5+1e2,maxd=2e1+1e1,maxp=7e1+1e1; 9 const int mod=232792561; 10 11 int k; 12 lli wpows[maxd]; 13 14 inline lli fastpow(lli base,int tim) { 15 lli ret = 1; 16 while( tim ) { 17 if( tim & 1 ) ret = ret * base % mod; 18 if( tim >>= 1 ) base = base * base % mod; 19 } 20 return ret; 21 } 22 23 struct Poly { 24 lli dat[maxd]; 25 Poly() { 26 memset(dat,0,sizeof(dat)); 27 } 28 inline void fill(int x) { // get point value expression , only p ^ x and p ^ 0 is 1 . 29 for(int i=0;i
1 //#include2 #include 3 //#include 4 //#include 5 //#define debug cout 6 typedef long long int lli; 7 //using namespace std; 8 const int maxn=1e6+1e2,lim=1e6; 9 10 lli phi[maxn],mem[maxn],vis[maxn];11 int n,mod,inv;12 13 inline lli fastpow(lli base,int tim) {14 lli ret = 1;15 while( tim ) {16 if( tim & 1 ) ret = ret * base % mod;17 if( tim >>= 1 ) base = base * base % mod;18 }19 return ret;20 }21 22 inline void sieve() {23 static int vis[maxn],prime[maxn],cnt;24 phi[1] = 1;25 for(int i=2;i<=lim;i++) {26 if( !vis[i] ) prime[++cnt] = i , phi[i] = i - 1;27 for(int j=1;j<=cnt&&(lli)i*prime[j]<=lim;j++) {28 const int tar = i * prime[j];29 vis[tar] = 1; 30 if( i % prime[j] ) phi[tar] = phi[i] * ( prime[j] - 1 );31 else {32 phi[tar] = phi[i] * prime[j];33 break;34 }35 }36 }37 for(int i=1;i<=lim;i++) ( phi[i] += phi[i-1] ) %= mod;38 }39 40 inline lli sumphi(lli x) {41 if( x <= lim )42 return phi[x];43 lli mp = n / x;44 if( vis[mp] )45 return mem[mp];46 lli ret = ( (lli) x ) * ( x + 1 ) >> 1;47 for(lli i=2,j;i<=x;i=j+1) {48 j = x / ( x / i );49 ret -= ( j - i + 1 ) * sumphi( x / i );50 }51 vis[mp] = 1;52 return mem[mp] = ret;53 }54 55 inline lli sum(lli x) {56 return x * ( x + 1 ) % mod * ( ( 2 * x + 1 ) % mod ) % mod * inv % mod;57 }58 inline lli segphi(lli l,lli r) {59 return ( sumphi(r) - sumphi(l-1) + mod ) % mod;60 }61 inline lli calc(lli n) {62 lli ret = 0;63 for(lli i=1,j;i<=n;i=j+1) {64 j = n / ( n / i );65 ( ret += segphi(i,j) * sum( n / i ) % mod ) %= mod;66 }67 return ret;68 }69 70 int main() {71 scanf("%d%d",&n,&mod) , sieve();72 inv = fastpow(6,mod-2);73 printf("%lld\n",calc(n));74 return 0;75 }
1 //#include2 #include 3 #include 4 //#include 5 #include 6 //#define debug cout 7 typedef long long int lli; 8 //using namespace std; 9 const int maxn=1e2+1e1,maxq=1e5+1e2;10 11 struct ACautomatic {12 int ch[maxn][26],fail[maxn],deg[maxn],sum[maxn],tim[maxn],root,cnt;13 ACautomatic() { root = ++cnt; }14 inline void insert(char* s,int li) {15 int now = root;16 for(int i=1;i<=li;i++) {17 const int t = s[i] - 'a';18 if( !ch[now][t] ) ch[now][t] = ++cnt;19 now = ch[now][t];20 }21 //debug<<"now = "< <