Multiplicative　Functions（与华科的友谊赛）--本人ACM小菜~略水略水

	站点公告

	用户登陆

站点日历

<< < 2013 - 8 > >>
日	一	二	三	四	五	六
				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

	我的相册

	最新日志

	最新评论

	日志搜索

	最新留言

	我的好友

	我的圈子

	友情链接

	站点统计

[ 2013-8-18 17:18:00 | By: acm_letgo ]

Multiplicative Functions（与华科的友谊赛）

今天与华科的友谊赛，5小时。果断被虐出翔啊。

不过我做的一个题目还是挺有收货的呢。

题目描述：

Description

In number theory, a multiplicative function is an arithmetic function F(n) of the positive integer n with property that F(1) = 1 and whenever a and b are coprime (gcd(a, b) = 1), then F(ab) = F(a)F(b).

The function E(n) defined by E(n) = 1 if n = 1 and = 0 if n > 1, is sometimes called multiplication unit for Dirichlet convolution or simply the unit function. If F and G are two multiplicative functions, one defines a new multiplicative function F * G, the Dirichlet convolution of F and G, by

where the sum extends over all positive divisors d of n. With this operation, the set of all multiplicative functions turns into an abelian group; the identity element is E.

from Wikipedia, the free encyclopedia

In this task you have to find the inverse of a multiplicative function. To cope with overflow problem, we define arithmetic functions as: F:N —> Z₂₀₀₇ where N is the set of positive integers, and Z₂₀₀₇ is a residue ring (ring of integers 0–2006, where arithmetic operations + and × are performed modulo 2007). Function G is called the inverse of function F if and only if F * G = G * F = E.

You are given the first N values of function F, you need to find the first N values of the inverse function G.

Input

In the first line of the input one number N is written (1 ≤ N ≤ 10⁴). In the second line values F(1), F(2), F(3), …, F(N) are listed. Numbers are separated by spaces. (Each value is nonnegative and doesn't exceed 2006.)

Output

In the first line of the output print first N values of inverse function G, separated by spaces: G(1), G(2), …, G(N).

Sample Input

input	output
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	1 2006 2006 0 2006 1 2006 0 0 1 2006 0 2006 1 1 0

你看得懂题目意思吗？如果你在半小时内看不懂题目意思，那么我很高兴，我的英语和你是一个级别的。不过也不该这么说，我个人觉得这个题目描述很垃圾，我真心看了半个小时才懂得。

比赛时，华科有的队伍很快就把这个题目砍掉了。我看题好久够终于也1A了。

题目的意思是定义F和G两个函数

给你每个F（1-n）的值，求其逆函数G的值

要求满足F*G=E(i=0是,E=1;i=1是E=0)

看懂题目后就知道这是个水题了。

稍加思考，显然就是一个扩展欧几里得解同余方程的题目嘛。

假设我们已经把G（1....i-1）求好了，现在要求Gi

这样我们只要枚举每个i的因子，列出方程，方程里面只有Gi一个未知量，带入扩展欧几里得模板就得出答案了呢。

下面上代码：

＃i nclude <iostream>
＃i nclude <cstdio>
＃i nclude <cstring>
#define ll long long
#define maxn 10100
#define M 2007
using namespace std;

ll f[maxn],g[maxn],n,i,j,a,b,d,x,y,tep,c;

void exgcd(ll a,ll b,ll& d,ll& x,ll& y)//扩展欧几里得模板
{
    if (b==0) { d=a,x=1,y=0; }
    else { exgcd(b,a%b,d,y,x); y-=(a/b)*x; }
}

int main()
{
    cin>>n;
    for (i=1; i<=n; i++) cin>>f[i];
    a=f[1],b=M,c=1;
    exgcd(a,b,d,x,y);
    g[1]=(x%M+M)%M;
    for (i=2; i<=n; i++)
    {
        tep=0;
        for (j=2; j*j<i; j++)
        {
            if (i%j!=0) continue;
            tep+=f[j]*g[i/j]+f[i/j]*g[j];
            tep%=M;
        }//把已知量求和，减掉
        if (j*j==i) tep+=f[j]*g[j];
        tep+=f[i]*g[1];
        tep=M-(tep%M);
        a=f[1],b=M,c=tep;
        exgcd(a,b,d,x,y);
        g[i]=(tep/d)*x;
        g[i]=(g[i]%M+M)%M;
    }
    cout<<g[1];
    for (i=2; i<=n; i++) cout<<' '<<g[i];
    cout<<endl;
    return 0;
}