首页 > 其他 > 详细

bzoj4833

时间:2018-02-17 23:07:58      阅读:134      评论:0      收藏:0      [点我收藏+]

标签:esp   pos   --   abd   pow   main   names   char   分享图片   

$数论$

$这个题已经忘了怎么做了,也不想知道了,只记得看了3个小时$

$对于有gcd(f_i, f_j) = f_{gcd(i, j)}性质的数列,以下结论适用$

技术分享图片
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n;
ll ans = 1, P;
ll f[N], g[N];
int m[N];
int rd()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < 0 || c > 9) { if(c == -) f = -1; c = getchar(); }
    while(c >= 0 && c <= 9) { x = x * 10 + c - 0; c = getchar(); }
    return x * f;
}
ll power(ll x, ll t)
{
    ll ret = 1;
    for(; t; t >>= 1, x = x * x % P) if(t & 1) ret = ret * x % P;
    return ret;
}
ll inv(ll x) 
{
    return power(x, P - 2);
}
int main()
{
    int T = rd();
    while(T--)
    {
        n = rd();
        P = rd();
        f[0] = 0;
        f[1] = 1;   
        for(int i = 2; i <= n; ++i) f[i] = (f[i - 1] * 2 + f[i - 2]) % P;
        for(int i = 1; i <= n; ++i) g[i] = f[i];
        for(int i = 1; i <= n; ++i) 
        {
            ll t = inv(g[i]);
            for(int j = i + i; j <= n    ; j += i)
                g[j] = g[j] * t % P;
        }
        ll lcm = 1;
        ans = 0;
        for(int i = 1; i <= n; ++i) 
        {
            lcm = lcm * g[i] % P;
            ans = (ans + 1LL * lcm * i) % P;    
        }
        printf("%lld\n", ans);
    }
    return 0;
}
View Code

 

bzoj4833

标签:esp   pos   --   abd   pow   main   names   char   分享图片   

原文:https://www.cnblogs.com/19992147orz/p/8452289.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号