专栏首页算法修养HDU 4059 The Boss on Mars(容斥原理)

HDU 4059 The Boss on Mars(容斥原理)

The Boss on Mars

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2494    Accepted Submission(s): 775

Problem Description

On Mars, there is a huge company called ACM (A huge Company on Mars), and it’s owned by a younger boss. Due to no moons around Mars, the employees can only get the salaries per-year. There are n employees in ACM, and it’s time for them to get salaries from their boss. All employees are numbered from 1 to n. With the unknown reasons, if the employee’s work number is k, he can get k^4 Mars dollars this year. So the employees working for the ACM are very rich. Because the number of employees is so large that the boss of ACM must distribute too much money, he wants to fire the people whose work number is co-prime with n next year. Now the boss wants to know how much he will save after the dismissal.

Input

The first line contains an integer T indicating the number of test cases. (1 ≤ T ≤ 1000) Each test case, there is only one integer n, indicating the number of employees in ACM. (1 ≤ n ≤ 10^8)

Output

For each test case, output an integer indicating the money the boss can save. Because the answer is so large, please module the answer with 1,000,000,007.

Sample Input

2
4
5

Sample Output

82
354
这道题目是求小于n和n互质的数的四次方的和
利用容斥原理,可以用总和减去不和n互质的和也可以直接求互质的数的和这里还涉及到了sum{1^4,2^4,3^4....n^4}求和公式n*(n+1)*(2*n+1)*((3*n*n+3*n-1)/30求和公式里有/ 那么在用同余定理的时候就要用逆元b/c(mod m)=b(mod m)* c^(m-2)(mod m)证明略#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
typedef long long int LL;
#define MAX 1000000
LL prime[MAX+5];
LL sprime[MAX+5];
bool check[MAX+5];
const LL mod=1e9+7;
LL INF;
LL cnt;
LL quick(LL x,LL a)
{
    LL sum=1;
    for(x;x>0;x>>=1)
    {
        if(x&1) 
			sum=(sum*a)%mod;
         a=(a*a)%mod;
    }
    return sum;
}
LL sum1(LL n)
{
    INF=quick(mod-2,30);
    return n*(n+1)%mod*(2*n+1)%mod*((3*n*n%mod+3*n-1)%mod)%mod*INF%mod;
}
LL sum2(LL n)
{
    return (((n*n)%mod*n)%mod*n)%mod;
}
void eular()
{
    memset(check,false,sizeof(check));
    int tot=0;
    for(LL i=2;i<MAX+5;i++)
    {
        if(!check[i])
            prime[tot++]=i;
        for(int j=0;j<tot;j++)
        {
            if(i*prime[j]>MAX+5) break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
void Divide(LL n)
{
    cnt=0;
    LL t=(LL)sqrt(n*1.0);
    for(LL i=0;prime[i]<=t;i++)
    {
        if(n%prime[i]==0)
        {
            sprime[cnt++]=prime[i];
            while(n%prime[i]==0)
                n/=prime[i];
        }
    }
    if(n>1)
        sprime[cnt++]=n;
}
int main()
{
    eular();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL n;
        scanf("%lld",&n);
        Divide(n);
  
        LL ans=0;
        LL res=sum1(n);
        for(int i=1;i<((LL)(1<<(cnt)));i++)
        {
            int num=0;
            LL tmp=1;
            for(int j=0;j<cnt;j++)
            {
                if(i&(1<<j))
                {
                    num++;
                    tmp*=sprime[j];
                }
            }
            if(num&1)
                ans=(ans+(sum1(n/tmp)*sum2(tmp))%mod)%mod;
            else
                ans=((ans-(sum1(n/tmp)*sum2(tmp))%mod)%mod+mod)%mod;
        }
        printf("%lld\n",(res-ans+mod)%mod);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ 2773 Happy 2006(容斥原理+二分)

    Happy 2006 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 1...

    ShenduCC
  • LeetCode 258. Add Digits

    同余定理,任何一个10进制数n 都可以表示成 n = a10^x + b10^(x-1) + .... c*10^0

    ShenduCC
  • HDU 1695 GCD (欧拉函数,容斥原理)

    GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

    ShenduCC
  • HDU----(4291)A Short problem(快速矩阵幂)

    A Short problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

    Gxjun
  • P2485 [SDOI2011]计算器

    题目描述 你被要求设计一个计算器完成以下三项任务: 1、给定y、z、p,计算y^z mod p 的值; 2、给定y、z、p,计算满足xy ≡z(mod p)的最...

    attack
  • 整除分块思想

    对于求形如 \(\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor\) 的值,就需要用到整除分块,否则当n很大时就会超时。在普通的一...

    _DIY
  • Git的使用--如何安装和使用 github,让小白不在那么白 (一)(超详解) 简介

      刚开始写了关于如何将本地代码上传到github上,但是有些小伙伴们不清楚如何安装Git,这一篇就给小伙伴们普及一下Git的安装和使用。适合刚开始用git的小...

    北京-宏哥
  • 数位DP - HDU 2089

    其实数位DP就是优化计数的过程,就是dfs+记忆化数组,题目会给一个上界或者下界,然后让你统计范围内符合要求的数量,如果事事用爆破的话就太有病了!除非我吃拧了!...

    ACM算法日常
  • C++核心准则C.162:将大致相同的操作设计为重载函数​

    Having different names for logically equivalent operations on different argument...

    面向对象思考
  • 下载并安装Git

    上篇 我们学习了什么是 Git 和 Github,回顾一下,Git 是一个工具,用来做版本控制,Github 是一个网站,基于云托管我们的代码,可以进行版本管理...

    Sharonyao

扫码关注云+社区

领取腾讯云代金券